Untitled

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1}, dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const int mod = 1e9+7; // 1e9+7, 998244353;
const double EPS = 1e-8;

int n, m, p;
vector <int> sp;
vector <ll> money;
vector <vector <ll>> dp;
vector <vector <ll>> adj;
ll go(int cur = 0, int msk = 1)
{
    if (msk == (1<<p)-1) return -adj[cur][0];
    auto &ret = dp[cur][msk];
    if (~ret) return ret;
    ret = -adj[cur][0];
    for (int i = 0; i < p; i++) {
        if (!(msk>>i&1)) {
            ret = max(ret, money[i]-adj[cur][sp[i]]+go(sp[i], msk|(1<<i)));
        }
    }
    return ret;
}

void burn(int tc)
{
    cin >> n >> m; n++;
    adj.assign(n, vector <ll> (n, 2e18));
    for (int i = 0; i < n; i++) adj[i][i] = 0;
    while(m--) {
        int u, v; cin >> u >> v;
        string s; cin >> s;
        s.erase(s.begin()+s.find('.'));
        adj[u][v] = min(adj[u][v], stoll(s));
        adj[v][u] = min(adj[v][u], adj[u][v]);
        adj[u][v] = min(adj[u][v], adj[v][u]);
    }
    for (int mi = 0; mi < n; mi++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                adj[i][j] = min(adj[i][j], adj[i][mi]+adj[mi][j]);
            }
        }
    }
    cin >> p;
    money.assign(n, 0);
    sp.clear();
    sp.push_back(0);
    for (int i = 0; i < p; i++) {
        int u; cin >> u;
        string s; cin >> s;
        s.erase(s.begin()+s.find('.'));
        money[sp.size()]+=stoll(s);
        sp.push_back(u);
    }
    p++;
    dp.assign(n, vector <ll> ((1<<p), -1));
    ll ans = go();
    string rem = to_string(ans%100);
    if (ans%100 < 10) rem = "0"+rem;
    if (ans > 0) cout << "Daniel can save $" << ans/100 << '.' << rem;
    else cout << "Don't leave the house";
}

int main()
{
    AboTaha_on_da_code

//    freopen("zeros.in", "r", stdin);
//    freopen("Aout.txt", "w", stdout);

    int T = 1; cin >> T;

    for (int i = 1; i <= T; i++) {
//        cout << "Case " << i << ":\n";
//        if (i > 1) cout << '\n';
        burn(i);
        cout << '\n';
    }
    return 0;
}