#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];
vector<int> T[N];
int par[N];
bool on[N];
void DFS(int u){
	on[u]=true;
	for(int v:T[u]){
		if(!on[v]){
			DFS(v);
		}
	}
}

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;
		int cnt=0;
		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;
				T[par[i]].pb(i);
				ans+=E[i][0].second;
				cnt++;
			}
		}
		ll sol=inf;
		if(cnt==n-1)sol=ans;

		if(y!=1){
			ans+=z;
			cnt++;
			if(par[y]!=0){
				ans-=E[y][0].second;
				cnt--;
			}
			bool cyc=false;
			for(int u=x;u!=0;u=par[u]){
				if(u==y)cyc=true;
			}
			if(!cyc){
				sol=min(sol,ans);
			}else{
				DFS(y);
				for(int u=x;u!=y;u=par[u]){
					ll delta=-E[u][0].second;
					if(cnt==n){
						sol=min(sol,ans+delta);
					}else{
						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();
			T[i].clear();
			par[i]=0;
			on[i]=false;
		}
	}
	return 0;
}