#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()

const int inf = 1e9 + 7;


void dfs(int u, vector<int>& used, vector<vector<int>>& g) {
    used[u] = 1;
    for (int i : g[u]) {
        if (!used[i]) {
            dfs(i, used, g);
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;


    vector<vector<pair<int, int>>> g(n);
    vector<vector<pair<int, int>>> ag(n);


    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].push_back({b, c});
        ag[b].push_back({a, c});
    }

    vector<pair<int, int>> be(n);
    vector<vector<int>> gg(n);

    ll sum = 0;

    int bad_one = -1;

    for (int i = 1; i < n; ++i) {
        pair<int, int> bei = {-1, inf};
        for (auto p : ag[i]) {
            if (p.second < bei.second) {
                bei = p;
            }
        }
        be[i] = bei;


        gg[be[i].first].push_back(i);
        sum += be[i].second;
        if (be[i].first > i) {
            bad_one = i;
        }
    }

    vector<int> used(n);
    dfs(0, used, gg);

    bool ok = 1;
    for (int i = 0; i < n; ++i) {
        if (used[i] == 0) ok = 0;
    }

    if (ok) {
        cout << sum << '\n';
        return;
    }

    vector<int> in_c(n);
    in_c[bad_one] = 1;
    for (int j = be[bad_one].first; j != bad_one; j = be[j].first) {
        in_c[j] = 1;
    }

    int mind = inf;
    for (int i = 0; i < n; ++i) {
        if (!in_c[i]) continue;
        for (auto p : ag[i]) {
            if (!used[p.first]) continue;
            mind = min(mind, p.second - be[i].second);
        }
    }

    cout << sum + mind << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    return 0;
}