#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;
mt19937 rnd(234);


struct edge {
    int to;
    ll w;
};


bool operator<(const edge& a, const edge& b) {
    return a.w < b.w;
}


int n, m;
int a, b;
ll x;
vector<vector<edge>> g;



int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t;
    cin >> t;
    for (int itr = 0; itr < t; itr += 1) {
        cin >> n >> m;
        g.assign(n, vector<edge>());
        a = -1;
        for (int i = 0; i < m; i += 1) {
            int u, v;
            ll w;
            cin >> u >> v >> w;
            --u;
            --v;
            if (u < v) {
                g[v].push_back(edge{ u, w });
            } else {
                a = v;
                b = u;
                x = w;
            }
        }
        assert(a != -1);
        for (int i = 0; i < n; i += 1) {
            sort(all(g[i]));
        }
        ll sm = 0;
        bool ok = true;
        ll rs = inf;
        for (int i = n - 1; i >= 1; i -= 1) {
            if (g[i].empty()) {
                ok = false;
                assert(i == a);
            } else {
                sm += g[i][0].w;
            }
        }
        if (ok) {
            rs = min(rs, sm);
        }
        if (a == 0 || a == b) {
            assert(ok);
            cout << rs << "\n";
            continue;
        }
        if (!g[a].empty()) {
            sm -= g[a][0].w;
        }
        sm += x;
        vector<int> usd(n, false);
        int t = b;
        while (t > a) {
            usd[t] = true;
            t = g[t][0].to;
        }
        if (t != a) {
            rs = min(rs, sm);
        } else {
            usd[a] = true;
            ll d = inf;
            for (int i = 0; i < n; i += 1) {
                if (!g[i].empty()) {
                    int to = g[i][0].to;
                    if (usd[to]) {
                        usd[i] = true;
                    }
                }
            }
            for (int i = 0; i < n; i += 1) {
                if (usd[i] && i != a) {
                    for (auto [to, w] : g[i]) {
                        if (!usd[to]) {
                            d = min(d, w - g[i][0].w);
                        }
                    }
                }
            }
            rs = min(rs, sm + d);
        }
        cout << rs << "\n";
    }
    return 0;
}

/*
3
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
4 4
1 2 4
1 3 6
1 4 8
4 2 1000000
3 3
1 2 100
2 1 10
2 3 1000


*/