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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


//#pragma GCC optimize("O3,unroll-loops")
#define migmig     		ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;


const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int inf = 1e9 + 90;
const int maxLG = 20;
const int SQ = 350;

ll n, m, dist[MAXN];
vector<pll> G[MAXN];
bool mark[MAXN];
set<pii> se;
ll MST = 0;

inline void add(int v) {
	for (auto [u, w] : G[v]) {
		if (!mark[u]) {
	      se.erase({dist[u], u});
	      se.insert({(dist[u] = w), u});
    	}
	}
}


inline void prim() {
	dist[1] = 0;
	add(1);
	se.insert({0, 1});
	for (int i = 1; i <= n; i++) {
		if (se.empty()) {
			return;
		}
		auto tmp = *(se.begin());
		ll v = tmp.S;
		MST += tmp.F;
		se.erase(tmp);
		add(v);
		mark[v] = 1;
	}
}

int main() {
	migmig;
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		memset(dist, 63, sizeof dist);
		int b, tmp;
		vector<pair<pii, int>> edg;
		for (int i = 1; i <= m; i++) {
			ll v, u, w;
			cin >> v >> u >> w;
			if (v > u) {
				b = u;
				tmp = w;
			}
			G[v].pb({u, w});
			edg.pb({{v, u}, w});
		}
		G[b].cl();
		prim();
//		deb(MST);
		int res1 = MST + tmp;
		int res2;
//		cout << MST + tmp << endl;
		MST = 0;
		for (int i = 1; i <= n; i++)
			G[i].cl();
			
		memset(dist, 63, sizeof dist);
		se.cl();
		memset(mark, false, sizeof mark);
		
		for (auto x : edg) {
			int v = x.F.F, u = x.F.S, w = x.S;
			if (v < u)
				G[v].pb({u, w});
		}
		prim();
		int res1 = MST;
		for (int i = 1; i <= n; i++)
			G[i].cl();
			
		memset(dist, 63, sizeof dist);
		se.cl();
		memset(mark, false, sizeof mark);
		cout << min(res1, res2) << endl;
	}
}

/*
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
*/

answer.code: In function ‘void add(int)’:
answer.code:38:19: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   38 |         for (auto [u, w] : G[v]) {
      |                   ^
answer.code: In function ‘int main()’:
answer.code:81:41: warning: narrowing conversion of ‘w’ from ‘ll’ {aka ‘long long int’} to ‘int’ [-Wnarrowing]
   81 |                         edg.pb({{v, u}, w});
      |                                         ^
answer.code:103:21: error: redeclaration of ‘int res1’
  103 |                 int res1 = MST;
      |                     ^~~~
answer.code:86:21: note: ‘int res1’ previously declared here
   86 |                 int res1 = MST + tmp;
      |                     ^~~~