#include <bits/stdc++.h>
using namespace std;

struct Step {
    int to;
    long long d;
    Step(int t, long long dd) : to(t), d(dd) {}
    bool operator<(const Step &o) const {
        return d > o.d;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n);
    vector<int> min_in(n, INT_MAX);
    int start, end, wb;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        if (u < v) {
            graph[u].emplace_back(v, w);
            min_in[v] = min(min_in[v], w);
        } else {
            start = u;
            end = v;
            wb = w;
        }
    }
    vector<long long> psum(n);
    for (int i = 1; i < n; i++) {
        psum[i] = psum[i - 1] + (min_in[i] == INT_MAX ? 0 : min_in[i]);
    }

    long long mst1 = 0;
    bool mst1_possible = true;
    for (int i = 1; i < n; i++) {
        if (min_in[i] == INT_MAX) {
            mst1_possible = false;
            break;
        }
        mst1 += min_in[i];
    }
    long long after_cost = 0;
    for (int i = start + 1; i < n; i++) {
        after_cost += min_in[i];
    }

    bool mst2_possible = (end > 0);
    long long mst2 = wb;
    if (mst2_possible) {
        vector<vector<pair<int, long long>>> g2(n);
        for (int i = 0; i < n; i++) {
            for (auto [to, w] : graph[i]) {
                if (to != start) {
                    g2[i].emplace_back(to, w + psum[to - 1] - psum[i]);
                }
            }
        }
        vector<long long> dists(n, LONG_LONG_MAX);
        priority_queue<Step> pq;
        pq.emplace(0, 0);
        while (!pq.empty()) {
            Step cur = pq.top();
            pq.pop();
            if (cur.d >= dists[cur.to]) {
                continue;
            }
            dists[cur.to] = cur.d;
            for (auto [nei, w] : g2[cur.to]) {
                if (nei <= start) {
                    pq.emplace(nei, cur.d + w);
                }
            }
        }
        if (dists[start] < LONG_LONG_MAX) {
            mst2 = dists[start] + after_cost;
        } else {
            mst2_possible = false;
        }
    }

    long long res = mst1;
    if (!mst1_possible || (mst2_possible && mst2 < mst1)) {
        res = mst2;
    }
    cout << res << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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