#include <bits/stdc++.h>

using namespace std;

using pii = array<int, 2>;
using e = array<int, 3>;

using graph = vector< vector<e> >;

long long prim(const graph & g, int to) {
    int n = g.size();
    const int INF = 2e9;
    vector<int> d(n, INF);
    d[0] = 0;
    priority_queue<pii, vector<pii>, greater<>> pq;
    pq.push({0, 0});
    vector<char> visited(n);
    vector<int> prev(n, -1);
    set<int> path;
    for (int _ = 0; _ < 2; ++_) {
        while (pq.size()) {
            auto [_, u] = pq.top();
            pq.pop();
            if (visited[u]) {
                continue;
            }
            visited[u] = true;
            for (auto [_, v, w] : g[u]) {
                if (w < d[v] && !visited[v] && !path.count(v)) {
                    d[v] = w;
                    prev[v] = u;
                    pq.push({d[v], v});
                }
            }
        }
        if (path.empty()) {
            while (prev[to] != -1) {
                path.insert(to);
                to = prev[to];
            }
            path.insert(to);
            to = -1;
            vector<int> d2(d);
            visited.assign(n, false);
            d.assign(n, INF);
            for (int el : path) {
                d[el] = d2[el];
                pq.push({d[el], el});
            }
        }
    }
    long long ans = 0;
    for (int el : d) {
        ans += el;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    e spec;
    vector<e> es;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;--v;
        es.push_back({u, v, w});
        if (u > v) {
            spec = {u, v, w};
        }
    }
    graph g1(n);
    for (auto [u, v, w] : es) {
        if (v == spec[1]) {
            continue;
        }
        g1[u].push_back({u, v, w});
    }
    g1[spec[0]].push_back(spec);

    graph g2(n);
    for (auto [u, v, w] : es) {
        if (u == spec[0] && v == spec[1]) {
            continue;
        }
        g2[u].push_back({u, v, w});
    }
    cout << min(prim(g1, spec[1]), prim(g2, spec[1])) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}