#include <iostream>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
	int n, m; cin >> n >> m;
	vector<vector<pair<int, ll>>> adj(n);
	int badU, badV, badW;
	for( int i = 0 ; i < m; i++) {
		int u, v; cin >> u >> v;
		u--;v--;
		ll w; cin >> w;
		adj[u].push_back({v, w});
		if (u > v) {
			badU = u;
			badV = v;
			badW = w;
		}
	}
	
	vector<bool> vis(n);
	minpq<pair<ll, int>> q;
	ll out = 0;
	q.push({0, 0});
	while (q.size()) {
		auto [w, i] = q.top();
		q.pop();
		if (vis[i]) continue;
		out += w;
		vis[i] = true;
		for (auto [j, w] : adj[i]) {
			if (j < i) continue;
			if (!vis[j]) {
				q.push({w, j});
			}
		}
	}
	vis.assign(n, 0);
	while (q.size()) q.pop();
	ll cur = badW;
	// find cheapest edge going into badU
	ll cost = 1e18;
	for (int i = 0; i < n; i++) {
		for (auto [to, cos] : adj[i]) {
			if (to == badU) cost = min(cost, cos);
		}
	}
	vis[badV] = true;
	cur += cost;
	q.push({0, 0});
	q.push({0, badU});
	while (q.size()) {
		auto [w, i] = q.top();
		q.pop();
		if (vis[i]) continue;
		cur += w;
		vis[i] = true;
		for (auto [j, w] : adj[i]) {
			if (!vis[j]) {
				q.push({w, j});
			}
		}
	}

	out = min(out, cur);
	cout << out << endl;
}

int main() {
	int t; cin >> t;
	while (t--) solve();
}