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

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[v].emplace_back(u, w);
            min_in[v] = min(min_in[v], w);
        } else {
            start = u;
            end = v;
            wb = w;
        }
    }

    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];
    }

    vector<int> chain_id(n);
    vector<int> prev_node(n);
    chain_id[0] = 1;
    chain_id[end] = 2;
    long long mst2 = wb;
    for (int i = 1; i < n; i++) {
        if (i != end) {
            int min_edge = INT_MAX;
            int p_node = -1;
            for (auto [prev, w] : graph[i]) {
                if (w < min_edge) {
                    min_edge = w;
                    p_node = prev;
                }
            }
            mst2 += min_edge;
            chain_id[i] = chain_id[p_node];
            prev_node[i] = p_node;
        }
    }

    bool mst2_possible = true;
    if (chain_id[start] == 2) {
        vector<bool> valid(n);
        int cur = start;
        while (cur != end) {
            valid[cur] = true;
            cur = prev_node[cur];
        }
        int min_change = INT_MAX;
        for (int i = end + 1; i <= start; i++) {
            if (valid[i]) {
                for (auto [prev, w] : graph[i]) {
                    if (chain_id[prev] == 1) {
                        min_change = min(min_change, w - min_in[i]);
                    }
                }
            }
        }
        if (min_change == INT_MAX) {
            mst2_possible = false;
        } else {
            mst2 += min_change;
        }
    }

    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();
    }
}