#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(int i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

ll t,n,m,in[maxn],l,r,wl,dp[maxn], pf[maxn];
vector<pair<ll,ll>> G[maxn];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> t;
    while(t--){
        cin >> n >> m;
        f1(i,n) {
            in[i] = inf;
            dp[i] = inf;
        }
        f1(i,m){
            ll u, v, w; cin >> u >> v >> w;
            if(u > v){
                l = v; r = u; wl = w;
                continue;
            }
            G[v].push_back({u, w});
            in[v] = min(in[v], w);
        }
        in[1] = 0;
        // Case 1: do not take reversal
        ll ans1 = 0;
        f1(i,n) {
            ans1 += in[i];
            pf[i] = pf[i-1] + in[i];
        }
        // Case 2:
        ll ans2 = wl;
        f1(i,l-1) ans2 += in[i];
        for(ll i=r+1;i<=n;i++) ans2 += in[i];
        for(ll u=l+1;u<=r;u++){
            for(pair<ll,ll> e: G[u]){
                ll c = e.first, w = e.second;
                if(c < l){
                    dp[u] = min(dp[u], w);
                }else if(c != l){
                    dp[u] = min(dp[u], dp[c] + w);
                }
            }
        }
        ans2 += dp[r];
        cout << min(ans1, ans2);el;
    }
    return 0;
}