#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 d[N];
vector<pair<int,ll>>mp[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];
    if(q==1){
        cout<<as<<'\n';
        return;
    }
    for(int i=1;i<=n;i++)d[i]=2e9;
    for(int i=1;i<=m;i++)if(a[i]<b[i]&&b[i]!=q)mp[b[i]].emplace_back(a[i],c[i]-ans[b[i]]);
    d[1]=0;
    for(int i=2;i<=p;i++)for(auto[x,j]:mp[i])d[i]=min(d[i],d[x]+j);
    cout<<min(as,as+r-ans[q]+d[p])<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--)solve();
}