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

#define ar array
#define F first
#define S second
typedef int uci;
#define int long long
#define ll long long

void solve(){
    ll T; cin >> T;
    for(ll t = 0; t < T; ++t) {
        ll N,M; cin >> N >> M;

        vector<vector<pair<ll,ll>>> incoming(N);

        ll ru,rv,rw;
        for(ll m = 0; m < M; m++) {
            ll U,V,W; cin >> U >> V >> W; U--; V--; W;

            if(U < V) incoming[V].push_back({U,W});
            else {ru = U; rv = V; rw = W;}
        }



        ll ans = 1000000000000000000;

        bool gd = true;
        ll noans = 0;
        for(ll i = 1; i < N; i++) {
            if(!incoming[i].size()) {gd = false; break;}
            ll c = incoming[i][0].S;
            for(ll j = 1; j < incoming[i].size(); j++) c = min(c,incoming[i][j].S);
            noans += c;
        }
        if(gd) ans = noans;



        gd=true;
        ll yeans = rw;
        vector<ll> DP(N,-1);
        if(rv == 0) {gd = false; goto skip;}        
        DP[0] = 0;
        for(ll i = 1; i < N; i++) {
            if(i == rv) continue;
            if(!incoming[i].size()) {gd = false; break;} // this shouldnt happen, but w/e.

            for(ll j = 0; j < incoming[i].size(); j++) {
                if(DP[incoming[i][j].F] >= 0) {
                    ll co = DP[incoming[i][j].F] + incoming[i][j].S;
                    if(DP[i] < 0) DP[i] = co;
                    else DP[i] = min(DP[i],co);
                }
            }
        }
        if(DP[ru] < 0) gd = false;
        else yeans += DP[ru];
        skip:
        if(gd) ans = min(ans, yeans);

        cout << ans << "\n";


    }
}

uci main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    solve();
}