#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef array<int, 3> ai3;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const int Mod = 147744151;
const int inv[5] = {0, 1, (Mod+1) / 2, (Mod+1) / 3};
inline int sign(int a){ return (a&1) ? (Mod-1) : 1; }
inline void uadd(int &a, int b){ a += b-Mod; a += (a>>31) & Mod; }
inline void usub(int &a, int b){ a -= b, a += (a>>31) & Mod; }
inline void umul(int &a, int b){ a = (int)(1ll * a * b % Mod); }
inline int add(int a, int b){ a += b-Mod; a += (a>>31) & Mod; return a; }
inline int sub(int a, int b){ a -= b, a += (a>>31) & Mod; return a; }
inline int mul(int a, int b){ a = (int)(1ll * a * b % Mod); return a; }
int qpow(int b, int p){ int ret = 1; while(p){ if(p&1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
const int fN = 111;
int fact[fN], invfact[fN], pw2[fN], invpw2[fN];
void initfact(int n){
	pw2[0] = 1; for(int i = 1; i <= n; ++i) pw2[i] = mul(pw2[i-1], 2);
	invpw2[0] = 1; for(int i = 1; i <= n; ++i) invpw2[i] = mul(invpw2[i-1], (Mod+1) / 2);
	fact[0] = 1; for(int i = 1; i <= n; ++i) fact[i] = mul(fact[i-1], i);
	invfact[n] = qpow(fact[n], Mod-2); for(int i = n; i > 0; --i) invfact[i-1] = mul(invfact[i], i);
}
int binom(int n, int m){ return (m < 0 || m > n) ? 0 : mul(fact[n], mul(invfact[m], invfact[n-m])); }
const double pi = acos(-1);
inline void chmax(int &a, int b){ (b>a) ? (a=b) : 0; }
inline void chmin(int &a, int b){ (b<a) ? (a=b) : 0; }

int n, m;
vector<pii> rg[200200];
ll f[200200];
void solve(){
	cin >> n >> m;
	rep(i, n) rg[i].clear();
	int su = -1, sv = -1, sw;
	rep(i, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		if(u > v)
			su = u, sv = v, sw = w;
		else
			rg[v].push_back(make_pair(w, u));
	}
	rep(i, n) sort(rg[i].begin(), rg[i].end());
	ll ans = 0, sum = 0;
	for(int i = 1; i < n; ++i){
		if(rg[i].empty()){
			ans = inf;
		} else 
			sum += rg[i][0].first;
	}
	if(ans < inf) ans = sum;
	if(su >= 0){
		rep(i, sv) f[i] = 0;
		f[sv] = inf;
		for(int i = sv + 1; i <= su; ++i){
			f[i] = inf;
			for(auto p : rg[i]){
				f[i] = min(f[i], f[p.second] + (p.first - rg[i][0].first));
			}
		}
		ans = min(ans, sum - (rg[sv].empty() ? 0 : rg[sv][0].first) + f[su] + sw);
	}
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	while(T--)
		solve();

	return 0;
}