#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],G[N];
int pre[N];
int dijkstra(int n,int T)
{
    vector<int>dist(n+1,INF);
    vector<bool>st(n+1,0);
    dist[1]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,1});
    while(heap.size())
    {
        auto it = heap.top();
        heap.pop();
        int u = it.y;
        if(u==T)    return dist[T];
        if(st[u])   continue;
        st[u]=true;
        //cout<<u<<"!!!!!!\n";
        for(auto [x,y]:G[u])
        {
            if(dist[x]>dist[u]+y)
            {
                pre[x]=u;
                dist[x]=dist[u]+y;
                heap.push({dist[x],x});
                //cout<<x<<" "<<dist[x]<<"!!!!!\n";
            }
        }
    }
}
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        h[i].clear();
        G[i].clear();
        pre[i]=0;
    }
    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});
        G[u].push_back({v,w});
    }
    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;
    }
    for(int i=1;i<=n;i++)   st[i]=false;
    int u = tmp[0],v=tmp[1];
    ans = dijkstra(n,u);
    while(u!=1)
    {
        st[u]=true;
        u=pre[u];
    }
    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;
}