#include<bits/stdc++.h>

using namespace std;

struct edge {
    int w, u, v;
};
bool operator<(edge a, edge b) {
    return a.w < b.w;
}
struct DSU {
    int cnt;
    vector<int> p;
    DSU() = default;
    DSU(int n) : cnt(n), p(n, 0) {
        iota(p.begin(), p.end(), 0);
    }

    int get(int u) {
        return u == p[u] ? u : p[u] = get(p[u]);
    }

    bool unite(int u, int v) {
        u = get(u), v = get(v);
        if (u == v) return 0;
        --cnt;
        p[v] = u;
        return 1;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<edge> e;
    edge ss;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        if (u < v) e.push_back({w, u, v});
        else ss = {w, u, v};
    }
    sort(e.begin(), e.end());
    long long ans = LLONG_MAX;
    {
        DSU dsu(n);
        long long cur = 0;
        for (auto [w, u, v] : e) {
            cur += w * dsu.unite(u, v);
        }
        if (dsu.cnt == 1) ans = min(ans, cur);
    }
    {
        DSU dsu(n);
        long long cur = ss.w;
        for (auto [w, u, v] : e) {
            if (dsu.get(u) == dsu.get(ss.u) && dsu.get(v) == dsu.get(ss.v)) continue;
            cur += w * dsu.unite(u, v);
        }
        if (dsu.cnt == 1) ans = min(ans, cur);
    }
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) solve();
}