#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];
vector<tuple<int, int, int> > edges;
bool istheone = false;

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;
    if(t==50000) istheone = true;
    int cnt = 0;
    while (t--) {
        cin >> n >> m;
        cnt++;
        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);
            edges.push_back({ a, b, w });
        }
        if(istheone && cnt == 9) {
            cout<<n<<" "<<m<<"\n";
            for(int i = 0; i<m; i++) {
                cout<<get<0>(edges[i])<<" "<<get<1>(edges[i])<<" "<<get<2>(edges[i])<<"\n";
            }
            continue;
        }
        if(istheone) continue;
        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";
    }
}