#include <bits/stdc++.h>
using namespace std;
#define int long long
int mxn = 200005;
vector<vector<pair<int,int>>>adj(mxn); int ln = 20;
vector<vector<int>>dp(mxn,vector<int>(ln));
vector<int>weight(mxn);
vector<int>lvl(mxn);
struct DisjointSet{
    vector<int>parent,sz,mn,mx;
    int size;
    void init(int n){
        size = n;
        parent.resize(n+1); sz.resize(n+1); mx.resize(n+1); mn.resize(n+1);
        for(int i = 1; i<=n; i++){
            parent[i] = i;
            sz[i] = 1;
            mx[i] = i;
            mn[i] = i;
        }
    }
    int find(int x){
        if(parent[x]==x)return x;
        return find(parent[x]);
    }
    void Union(int x, int y){
        x = find(x); y = find(y);
        if(x==y)return;
        if(sz[x]<sz[y]){
            parent[x] = y;
            mx[y] = max(mx[y],mx[x]);
            mn[y] = min(mn[y],mn[x]);
            sz[y]+=sz[x];
        }
        else{
            parent[y] = x;
            sz[x]+=sz[y];
            mx[x] = max(mx[x],mx[y]);
            mn[x] = min(mn[x],mn[y]);
        }
    }
};

struct edge{
    int x,y,w;
};
bool comp(edge a, edge b){
    return a.w < b.w;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        DisjointSet ds;
        ds.init(n+1);
        edge p;
        vector<edge>alledges;
        vector<edge>edges;
        for(int i = 0; i<m; i++){
            int x,y,w;
            cin >> x >> y >> w;
            if(x>y){
                p = edge{x,y,w};
            }
            else{
                 edges.push_back(edge{x,y,w});
            }
            alledges.push_back(edge{x,y,w});
        }
        sort(edges.begin(),edges.end(),comp);
        int ans = 0;
        if(true){
            for(auto e: edges){
                int x = e.x; int y = e.y; int w = e.w;
                if(ds.find(x) == ds.find(y))continue;
                ds.Union(x,y);
                //cerr << x << ' ' << y << ' ' << w << '\n';
                ans+=w;
            }
        }
        int ans2 = p.w;
        swap(p.x,p.y);
        vector<edge>goodedges;
        DisjointSet ds2;
        ds2.init(n+1);
        ds2.Union(p.x,p.y);
        for(edge e: edges){
            if(e.y == p.y && e.x > p.x){
                continue;
            }
            goodedges.push_back(e);
        }
        sort(goodedges.begin(),goodedges.end(),comp);
        int cnt = 1;
        if(true){
            for(auto e: goodedges){
                int x = e.x; int y = e.y; int w = e.w;
                if(ds2.find(x) == ds2.find(y))continue;
                ds2.Union(x,y);
                //cerr << x << ' ' << y << ' ' << w << '\n';
                ans2+=w;
                cnt++;
            }
        }
        if(cnt==n-1){
            cout << min(ans,ans2) << '\n';
        }
        else{
            cout << ans << '\n';
        }
    }
    return 0;
}