#include<bits/stdc++.h>
#define ll long long 
#define N 500005
using namespace std;
int T,n,m;
struct node{
    int u,v,w;
}e[N];
bool cmp(node a,node b){
    return a.w<b.w;
}
vector<pair<int,int> > pa[N];
vector<int> v[N];
int vis[N];
void dfs(int x){
    // cerr<<x<<endl;
    vis[x]=1;
    for(auto V:v[x])
        dfs(V);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;++i){
            pa[i].clear();
            v[i].clear();
            vis[i]=0;
        }
        int a,b,c;
        for(int i=1;i<=m;++i){
            cin>>e[i].u>>e[i].v>>e[i].w;
            if(e[i].u<e[i].v){
                pa[e[i].v].push_back(make_pair(e[i].w,e[i].u));
            }else{
                a=e[i].u,b=e[i].v,c=e[i].w;
            }
        }
        ll ans=0;
        bool fl=1;
        for(int i=2;i<=n;++i){
            sort(pa[i].begin(),pa[i].end());
            if(pa[i].size()==0) fl=0;
            else ans+=pa[i][0].first;
        }
        if(b!=1){
            ll nans=ans;
            if(fl==0) ans=1e18;
            else nans-=pa[b][0].first;
            nans+=c;
            // cerr<<nans<<endl;
            for(int i=2;i<=n;++i){
                if(pa[i].size()>0&&i!=b){
                    v[pa[i][0].second].push_back(i);
                }
            }
            // cerr<<"233\n";
            dfs(1);
            int pos=a;
            // cerr<<"pos "<<pos<<endl;
            while(pos!=b&&pos!=1){
                nans-=pa[pos][0].first;
                for(int i=0;i<pa[pos].size();++i)
                    if(vis[pa[pos][i].second]){
                        ans=min(ans,nans+pa[pos][i].first);
                    }
                nans+=pa[pos][0].first;                
                pos=pa[pos][0].second;
                // cerr<<"pos "<<pos<<'\n';
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}