#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
const int MAX = 4e5 + 10, mod = 998244353;

int n, m;
vector<pii> graph[MAX];
array<int, 3> spc;
bool vis[MAX];
int dp[MAX];
void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i) graph[i].clear(), dp[i] = 1e9;
	for (int i = 0; i < m; ++ i){
		int u, v, w;
		cin >> u >> v >> w;
		if (u > v) spc = {u, v, w};
		else graph[v].push_back({w, u});
	}
	for (int i = 1; i <= n; ++ i) sort(graph[i].begin(), graph[i].end());
	int ans1 = 0, ans2 = spc[2];
	for (int i = 2; i <= n; ++ i){
		if (graph[i].size() == 0) ans1 = 1e9;
		else ans1 += graph[i].front().first;
	}
	for (int i = 2; i <= n; ++ i){
		if (i == spc[1]) continue;
		if (graph[i].size() == 0) ans2 = 1e9;
		else ans2 += graph[i].front().first;
	}
	for (int i = spc[1] + 1; i <= spc[0]; ++ i){
		for (auto [w, u]: graph[i]){
			if (u < spc[1]) dp[i] = min(dp[i], w - graph[i].front().first);
			else dp[i] = min(dp[i], w - graph[i].front().first + dp[u]);
		}
	}
	ans2 += dp[spc[0]];
	if (spc[1] == 1) ans2 = 1e9;
	cout << min(ans1, ans2) << endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//cout << fixed << setprecision(7);
	int _;cin>>_;while (_ --)
		solve();
}