#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 = 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) {
            ll ans3 = 1e18;
            for (int v : path) {
                int mn2 = 2e9 + 9;
                for (auto [u, w] : g[v]) {
                    if (u == parent[v]) continue;
                    mn2 = min(mn2, w);
                }
                ans3 = min(ans3, ans2 + mn2 - weight[v]);
            }
            ans2 = ans3;
        }
        cout << min(ans, ans2) << '\n';
    }
}