#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const ll mod = 1e16 + 7;
const int N = 1e6 + 5;
vector<pair<int, ll>> adj[N];

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		adj[i].clear();
	array<ll, 3> e;
	e[2] = mod;
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		u--, v--;
		if (u > v)
			e = {u, v, w};
		else
			adj[v].push_back({u, w});
	}
	ll ans = 0;
	for (int i = 1; i < n; i++) {
		ll val = mod;
		for (auto [j, w]: adj[i])
			val = min(val, w);
		ans = min(mod, ans + val);
	}
	ll ans2 = e[2];
	vector<int> par(n), mn(n);
	vector<ll> out(n, mod);
	mn[e[1]] = e[1];
	for (int i = 1; i < n; i++) {
		if (i == e[1] || i == e[0])
			continue;
		ll val = mod;
		for (auto [j, w]: adj[i]) {
			if (w < val) {
				val = w;
				par[i] = j;
				mn[i] = mn[j];
			}
		}
		if (e[1] < i && i < e[0]) {
			for (auto [j, w]: adj[i]) {
				if (j < e[1])
					out[i] = min(out[i], w - val);
				else
					out[i] = min(out[i], out[j]);
			}
		}
		ans2 += val;
	}
	ll val = mod;
	for (auto [j, w]: adj[e[0]])
		val = min(val, w + out[j]);
	ans2 += val;
	if (e[1] == 0)
		ans2 = mod;
	cout << min(ans, ans2) << "\n";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t; cin >> t; while (t--) solve();
}