#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;
ll cnt = 0;

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


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

void reset() {
	memset(dist, 63, sizeof dist);
	for (ll i = 1; i <= n; i++)
			G[i].cl();
	memset(dist, 63, sizeof dist);
	se.cl();
	memset(mark, false, sizeof mark);
	MST = 0;
}

int main() {
	migmig;
	ll T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		reset();
		ll b, tmp;
		vector<pair<pll, ll>> edg;
		for (ll i = 1; i <= m; i++) {
			ll v, u, w;
			cin >> v >> u >> w;
			if (v > u) {
				b = u;
				tmp = w;
			}
			edg.pb({{v, u}, w});
		}
		
		
		for (auto x : edg) {
			ll v = x.F.F, u = x.F.S, w = x.S;
			if (v != b && u != b)
				G[v].pb({u, w});
		}
		prim();
//		deb(cnt);
		ll res1 = MST + tmp;
		if (cnt > n) {
			res1 = inf;
		}
		
		
		MST = 0;
		reset();
		ll c;
		for (auto x : edg) {
			ll v = x.F.F, u = x.F.S, w = x.S;
			if (v < u)
				G[v].pb({u, w});
		}
		cnt = 0;
		prim();
		ll res2 = MST;
//		deb(cnt);
		if (cnt > n) {
			res2 = inf;
		}
		cout << min(res1, res2) << endl;
		reset();
		
//		deb(res1 << ' ' << res2);
	}
}

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