#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;
#define int long long

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;
	}
}

#define ll long long

signed 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;
			}
			edg.pb({{v, u}, w});
		}
		for (auto [xx, w] : edg) {
			auto [v,u]  = xx;
			// v -> u
			if (v == b || u == b) {
				continue;
			}
			G[v].pb({u, w});
			edg.pb({{v, u}, w});
		}
		prim();
		int res1 = MST + tmp;
		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 res2 = 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) << '\n';
	}
}

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