#include <bits/stdc++.h>

using namespace std;

long long inf = numeric_limits<long long>::max()/3;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //ifstream cin("input.txt");
    long long t;
    cin>>t;
    while (t--){
        long long n,m;
        cin>>n>>m;
        long long left = -1;
        long long right = -1;
        long long weight = -1;
        vector<long long> best(n+1,inf);
        vector<vector<pair<long long,long long>>> adj_list(n+1);
        for (int i=0;i<m;i++){
            long long u,v,w;
            cin>>u>>v>>w;
            if (u>v){
                left = v;
                right = u;
                weight = w;
            }else{
                best[v] = min(best[v],w);
                adj_list[v].push_back({u,w});
            }
        }
        long long answer1 = 0;
        for (int i=2;i<=n;i++){
            if (best[i]==inf){
                answer1 = inf;
                break;
            }else{
                answer1 += best[i];
            }
        }
        long long answer2 = 0;
        for (int i=2;i<=n;i++){
            if (i==left){
                continue;
            }
            if (best[i]==inf){
                answer2 = inf;
                break;
            }
            for (int j=0;j<adj_list[i].size();j++){
                adj_list[i][j].second -= best[i];
                answer2 += best[i];
            }
        }
        priority_queue<pair<long long,long long>,vector<pair<long long,long long>>,greater<pair<long long,long long>>> pq;
        vector<long long> path(n+1,inf);
        pq.push({0,right});
        path[right] = 0;
        
        long long shortest_path;
        while (!pq.empty()){
            long long dist = pq.top().first;
            long long curr = pq.top().second;
            pq.pop();

            if (dist>path[curr]){
                continue;
            }
            if (curr==1){
                shortest_path = dist;
                break;
            }
            for (pair<long long,long long> child:adj_list[curr]){
                if (dist+child.second < path[child.first]){
                    path[child.first] = dist+child.second;
                    pq.push({path[child.first],child.first});
                }
            }
        }
        if (answer2==inf || shortest_path==inf){
            answer2 = inf;
        }else{
            answer2 += shortest_path + weight;
        }
        cout<<min(answer1,answer2)<<"\n";

    }
    return 0;
}
/*
1
3 2
1 3 10
3 2 10
*/