#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+7,M=5e5+7;
int T,n,m,vl[N],vl2[N],u[M],v[M],w[M],to[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=2;i<=n;i++)
            vl[i]=vl2[i]=to[i]=1e9+7;
        int uu,vv,ww;
        for(int i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i];
            if(u[i]==1)to[v[i]]=min(to[v[i]],w[i]);
            if(u[i]<v[i])vl[v[i]]=min(vl[v[i]],w[i]);
            else uu=u[i],vv=v[i],ww=w[i];
        }
        for(int i=1;i<=m;i++)if(u[i]!=uu){
            vl2[v[i]]=min(vl2[v[i]],w[i]);
        }
        int ans=0,ans2=0,op=1e9+7;
        for(int i=2;i<=n;i++){
            ans+=vl[i],ans2+=vl2[i];
            if(i!=vv)op=min(op,to[i]-vl2[i]);
        }
        ans2+=op;
        ans2+=ww-vl2[vv];
        cout<<min(ans,ans2)<<"\n";
    }
    return 0;
}