#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500013;
ll a[N],b[N],c[N];
int ans[N];
ll dif[N];
void solve(){
    int n,m;
    cin>>n>>m;
    int p=0,q=0,r=0;
    for(int i=1;i<=n;i++)ans[i]=2e9;
    for(int x,y,z,i=1;i<=m;i++){
        cin>>x>>y>>z;
        if(x<y)ans[y]=min(ans[y],z);
        else p=x,q=y,r=z;
        a[i]=x,b[i]=y,c[i]=z;
    }
    ll as=0;
    for(int i=2;i<=n;i++)as+=ans[i];
    for(int i=1;i<=n;i++)dif[i]=2e9;
    for(int i=1;i<=m;i++){
        if(a[i]<b[i]&&a[i]<q&&b[i]<=p&&b[i]>q)dif[b[i]]=min(dif[b[i]],c[i]-ans[b[i]]);
    }
    if(q==1){
        cout<<as<<'\n';
        return;
    }
    cout<<min(as,as+r-ans[q]+*min_element(dif+1+q,dif+p+1))<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--)solve();
}