#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mk make_pair
#define lowbit(x) (x&(-x))
#define pb emplace_back
#define pr pair<int,int>
#define let const auto
#define all(A) A.begin(),A.end()
const int N=2e5+5;
int read(){
	int x=0,f=1; char c=getchar();
	while(('0'>c||c>'9')&&c!='-') c=getchar();
	if(c=='-') f=0,c=getchar();
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return f?x:-x;
}
void solve(){
	int n=read(),m=read();
	vector <int> Min(n+1,0x3f3f3f3f),fa(n+1);
	vector <int> init(n+1),init2(n+1);
	vector <tuple <int,int,int> > edge;
	int su=9,sv=9,val=9;
	for(int i=1; i<=m; i++){
		int u=read(),v=read(),w=read();
		if(u>v) sv=v,su=u,val=w;
		else{
			edge.pb(u,v,w);
			if(w<Min[v]) Min[v]=w,fa[v]=u;
		};
	}
	ll ans=accumulate(Min.begin()+2,Min.end(),0ll);
	int res=0x3f3f3f3f;
	int p=su;
	while(p&&p!=sv) init[p]=1,p=fa[p];
	if(!p) fill(all(init),0),res=0;
	else{
		init2[sv]=1;
		for(int i=sv+1; i<=n; i++) init2[i]=init2[fa[i]];
	}
	for(auto [u,v,w]:edge) if(init[v]&&!init2[u]) res=min(res,w-Min[v]);
	
	printf("%lld\n",min(ans,ans-Min[sv]+val+res));
}
int main(){
	int T=read();
	while(T--) solve();
	return 0;
}