#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// if you end up using long double, you need to set the floating point notation to fixed, and set the percision to be very high
typedef long double ld;

// contrsuct umaps like this, unordered_map<long long, int, custom_hash> safe_map;
// FIXED_RANDOM is static so it doesn not get redeclared between function calls
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
		
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


#define INF 2001001001
#define INF2 2e18
#define MOD 1000000007

#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for(long long a = b; a < c; a++)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back 
#define pf push_front
#define f first
#define s second
#define mp make_pair
#define pll pair<ll, ll>
#define pint pair<int, int>
#define tp make_tuple

// first four are north, west, east ,south
int dir1[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dir2[] = {0, 1, 0, -1, 1, -1, 1, -1};

int n, m;
vector<vector<pll>> vec;
ll backwards[3];

int main() {
	// apparently this does fast i/o
	cin.tie(0) , ios::sync_with_stdio(0);
	
	// use this if you read in from a file
	/*
	freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
	*/
	
	stringstream ss;
	
	// Do it once. Do it right.
	// Read the problem statement carefully
	// Plan out the steps in words on a piece of paper before implementing
	// after RTE(obviously) but also WA, run valgrind!!!
	// Testing your solution on samples before coding is a great way to see if you read the problem correctly!!!
	// Also take notes about key elements in the problem statement while reading the problem!!!
	
	//cout << fixed << setprecision(12);
	// if you use ld, use the above and don't use string stream
	
	// use instead of ceil(a, b) if a and b are positive
	// (a + b - 1) / b
	
	int t;
	cin >> t;
	while(t > 0){
		t--;
		cin >> n >> m;
		vec.assign(n+1, vector<pll>());
		backwards[0] = 0, backwards[1] = 0;
		for(int i = 0; i < m; i++){
			ll u, v, w;
			cin >> u >> v >> w;
			vec[v].pb({u, w});
			if(u > v){
				backwards[0] = u;
				backwards[1] = v;
				backwards[2] = w;
			}
		}
		
		bool good1 = true;
		ll am1 = 0;
		for(int i = 2; i <= n; i++){
			ll minAm = INF2;
			for(auto p : vec[i]){
				if(i == backwards[1] && p.f == backwards[0]) continue;
				minAm = min(minAm, p.s);
			}
			if(minAm == INF2) good1 = false;
			else am1 += minAm;
		}
		
		vector<ll> dists(n+1, INF2);
		vector<bool> visited(n+1, false);
		vector<ll> backtrack(n+1, 0);
		
		dists[backwards[0]] = 0;
		priority_queue<pll, vector<pll>, greater<pll>> pq;
		pq.push(mp(0, backwards[0]));
		while (!pq.empty()) {
			int a = pq.top().s; 
			pq.pop();
			if (visited[a]) continue;
			visited[a] = true;
			for (auto e : vec[a]) {
				int b = e.first, w = e.second;
				if (dists[a]+w < dists[b]) {
					dists[b] = dists[a]+w;
					backtrack[b] = a;
					pq.push(mp(dists[b],b));
				}
			}
		}
		set<ll> done;
		int curr = 1;
		while(1){
			done.insert(curr);
			if(curr == backwards[0]) break;
			curr = backtrack[curr];
		}

		bool good2 = true;
		ll am2 = backwards[2] + dists[1];
		for(int i = 2; i <= n; i++){
			if(i == backwards[1] || done.count(i)) continue;
			ll minAm = INF2;
			for(auto p : vec[i]){
				minAm = min(minAm, p.s);
			}
			if(minAm == INF2) good2 = false;
			else am2 += minAm;
		}
		//cout << am1 << " " << am2 << "\n";
		if(good1 && good2){
			cout << min(am1, am2) << "\n";
		}else if(good1){
			cout << am1 << "\n";
		}else{
			cout << am2 << "\n";
		}
		
	}
	cout << ss.str();
	return 0;
}