#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 5e5+10;
const int INF = 1e15;
vector<PII>g[N],h[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        h[i].clear();
    }
    array<int,3> tmp;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(u>v) tmp={u,v,w};
        g[v].push_back({w,u});
    }
    for(int i=1;i<=n;i++)   sort(g[i].begin(),g[i].end());
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        int u = g[i][0].y,w=g[i][0].x;
        h[u].push_back({i,w});
        ans+=w;
    }
    vector<bool>st(n+1,0);
    queue<int>q;
    q.push(1);
    while(q.size())
    {
        int t = q.front();
        st[t]=true;
        q.pop();
        for(auto [x,y] : h[t])
        {
            if(st[x])   continue;
            q.push(x);
        }
    }
    bool ok = true;
    for(int i=1;i<=n;i++)
        if(!st[i])  ok=false;
    if(ok)
    {
        cout<<ans<<"\n";
        return;
    }
    ans=0;
    for(int i=1;i<=n;i++)   st[i]=false;
    int u = tmp[0],v=tmp[1],res=INF;
    while(true)
    {
        st[u]=true;
        for(auto [x,y]: g[u])
        {
            ans+=x;
            if(st[y])   ok=true;
            u=y;
            break;
        }
        if(ok)  break;
    }
    for(int i=1;i<=n;i++)
        if(st[i]&&g[i].size()>1)
            res=min(res,ans-g[i][0].x+g[i][1].x);
    ans=res;
    for(int i=2;i<=n;i++)
        if(!st[i])
            ans+=g[i][0].x;
    cout<<ans<<"\n";
}



signed main()
{
    int T=1;
    cin.tie(0)->sync_with_stdio(false);
    cin>>T;
    //init();
    while(T--) 
    {
        solve();
    }
    return 0;
}