#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=200050;
vector<pair<int,int>> E[N];
int par[N];
bool on[N];

const ll inf=1e18;
int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n,m;
		scanf("%i %i",&n,&m);
		int x,y,z;
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%i %i %i",&u,&v,&w);
			if(u>v){
				x=u;
				y=v;
				z=w;
			}else{
				E[v].pb({u,w});
			}
		}
		ll ans=0;
		bool ok=true;
		for(int i=2;i<=n;i++){
			sort(E[i].begin(),E[i].end(),[](pair<int,int> a,pair<int,int> b){return a.second<b.second;});
			if(E[i].size()){
				par[i]=E[i][0].first;
				ans+=E[i][0].second;
			}else{
				ok=false;
			}
		}
		ll sol=inf;
		if(ok)sol=ans;

		ans+=z;
		if(par[y]!=0){
			ans-=E[y][0].second;
		}
		bool cyc=false;
		for(int u=x;u!=0;u=par[u]){
			if(u==y)cyc=true;
		}
		if(!cyc){
			sol=min(sol,ans);
		}else{
			for(int u=x;u!=y;u=par[u]){
				on[u]=true;
			}
			on[y]=true;
			for(int u=x;u!=y;u=par[u]){
				ll delta=-E[u][0].second;
				ll mn=inf;
				for(int i=0;i<E[u].size();i++){
					if(!on[E[u][i].first]){
						mn=min(mn,(ll)E[u][i].second);
					}
				}
				sol=min(sol,ans+delta+mn);
			}
		}

		printf("%lld\n",sol);

		for(int i=1;i<=n;i++){
			E[i].clear();
			par[i]=0;
			on[i]=false;
		}
	}
	return 0;
}