#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e5 + 5;
int t, n, m, u, v, from[MAXN], in[MAXN];
pair<int, int> dist[MAXN];
vector<pair<int, int>> to[MAXN];

void reset() {
    for (int i = 1; i <= n; i++) {
        in[i] = 0;
        from[i] = 1e18;
        dist[i] = { 1e18, 0 };
        to[i].clear();
    }
}

signed main() {
    cin.tie(NULL)->sync_with_stdio(0);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        reset();
        for (int i = 0; i < m; i++) {
            int a, b, w;
            cin >> a >> b >> w;
            if (a > b) {
                u = b;
                v = a;
                continue;
            }
            to[a].push_back({ b, w });
            from[b] = min(from[b], w);
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if(from[i] != 1e18) ans += from[i];
        }
        int tot = 0;
        if(u==1){
            cout<<ans<<"\n";
            continue;
        }
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        pq.push({ 0, 1, 0 });
        while (pq.size()) {
            int d = get<0>(pq.top()), c = get<1>(pq.top()), p = get<2>(pq.top());
            pq.pop();
            if (dist[c].first <= d) continue;
            dist[c] = { d, p };
            for (auto& nxt : to[c]) {
                int v = nxt.first, w = nxt.second;
                if (d + w < dist[v].first && v != u) pq.push({ w, v, c });
            }
        }
        int c = v;
        while (c) {
            in[c] = 1;
            c = dist[c].second;
        }
        tot = dist[v].first;
        for (int i = 1; i <= n; i++) {
            if (!in[i]) tot += from[i];
        }
        cout << min(ans, tot) << "\n";
    }
}