#include <bits/stdc++.h>
using namespace std;
#define V vector
#define pb push_back
#define all0(x) (x).begin(), (x).end()
#define all0(x) (x).begin() + 1, (x).end()
#define fi first
#define se second
typedef pair<int, int> pi;
typedef long long LL;

const LL INFLL = 8e18 + 1000;

const int MN = 2e5 + 10;
int f[MN], siz[MN];
int par(int x) {
    if(x == f[x]) return x;
    return f[x] = par(f[x]);
}
void mer(int a, int b) {
    a = par(a), b = par(b);
    if(a == b) return ;
    f[a] = b;
    siz[b] += siz[a];
}
void ini(int n) {
    for(int i = 1; i <= n; i++) {
        f[i] = i, siz[i] = 1;
    }
}

void solve() {
    int n, m; cin >> n >> m;
    int a = -1, b;
    int c;
    V<array<int, 3>> E;
    for(int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        int w; cin >> w;
        if(x <= y) E.pb({x, y, w});
        else if(x != y && y != 1) a = y, b = x, c = w;
    }  
    LL ans = INFLL;
    ini(n);
    LL cur = 0;
    int cnt = 0;
    for(auto [x, y, w] : E) {
        if(par(x) != par(y)) {
            mer(x, y), cur += w, cnt++;
        }
    }
    if(cnt == n - 1) {
        ans = min(ans, cur);
    }
    if(a != -1) {
        ini(n);
        LL cur = c;
        int cnt = 0;
        for(auto [x, y, w] : E) {
            if(par(y) == par(a)) swap(x, y);
            if(par(x) != par(y) && !(par(x) == par(a) && (par(y) == par(b) || par(y) == par(1)))) {
                mer(x, y), cur += w, cnt++;
            }
        }
        if(cnt == n - 2) {
            ans = min(ans, cur);
        }
    }
    cout << ans << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while(t--) solve();
}