#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<pii>> g(n);
        int x, y, wxy;
        while (m--) {
            int u, v, w;
            cin >> u >> v >> w;
            --u; --v;
            if (u > v) {
                x = v, y = u, wxy = w;
            } else {
                g[v].push_back({u, w});
            }
        }
        ll ans = 0;
        vector<int> parent(n, -1), weight(n);
        for (int v = 1; v < n; ++v) {
            int mn = 2e9 + 9;
            int best = -1;
            for (auto& [u, w] : g[v]) {
                if (w < mn) {
                    mn = w;
                    best = u;
                }
            }
            parent[v] = best;
            weight[v] = mn;
            ans += mn;
        }
        ll ans2 = 1e18;
        if (x != 0) {
            ans2 = ans + wxy - weight[x];
            vector<int> path;
            bool ok = false;
            for (int v = y; v != x; v = parent[v]) {
                if (v == -1) {
                    ok = true;
                    break;
                }
                path.push_back(v);
            }
            if (!ok) {
                vector<int> bad(n, false);
                bad[x] = true;
                for (int v : path) {
                    bad[v] = true;
                }
                for (int v = 1; v < n; ++v) {
                    for (auto [u, _] : g[v]) {
                        if (bad[u]) {
                            bad[v] = true;
                        }
                    }
                }
                ll ans3 = 1e18;
                for (int v : path) {
                    int mn2 = 2e9 + 9;
                    for (auto [u, w] : g[v]) {
                        if (bad[u]) continue;
                        //if (u == parent[v]) continue;
                        mn2 = min(mn2, w);
                    }
                    if (mn2 <= 1e9) {
                        ans3 = min(ans3, ans2 + mn2 - weight[v]);
                    }
                }
                ans2 = ans3;
            }
        }
        cout << min(ans, ans2) << '\n';
    }
}