/*
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
*/
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define pii pair<int, int>
#define pil pair<int, ll>
const int maxn = 200003;
const ll mx = 1000000000000000000LL;
int n; int m;
//one rebellious edge, other edges all face in one direction
//if you don't use the edge, take the smallest connection of each node
//if you use the edge, skip the node that it goes back to when taking the smallest
 //connection of each node and then visit that node last

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    while(t--){
        cin >> n >> m;
        vector<vector<pil>> edg(n, vector<pil>());
        int rebelin = -1; int rebelout = -1; ll rebelv = 0LL; //skip rebelin
        vll dp(n, vl(2, mx));
        for(int a = 0; a < m; a++){
            int f; int s; ll v;
            cin >> f >> s >> v; f--; s--;
            if(f > s){
                rebelin = f; rebelout = s; rebelv = v;
            }
            else{
                edg[s].push_back({f, v});
            }
        }

        vl s(2, 0);
        for(int a = 0; a < 2; a++){
            for(int b = 1; b < n; b++){
                if(a == 1 && b == rebelout) continue;
                int echose = -1;
                for(pil e : edg[b]){
                    if(dp[b][a] > e.second) echose = e.first;
                    if(a == 1 && e.first == rebelout && b <= rebelin) continue;
                    dp[b][a] = min(dp[b][a], e.second);
                }
                //cout << " chose " << echose << " to " << b << " parity " << a << endl;
                s[a] += dp[b][a];
            }
        }
        cout << min(s[0], s[1] + rebelv) << "\n";
    }
}