/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int fa[200005];
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
	int xx=find(x),yy=find(y);
	if(xx!=yy) fa[xx]=yy;
}
vector <pii > g[200005];
int dist[200005];
int calc(int n,vector <array<int,3> > vec,int lim)
{
	for(int i=1;i<=n;i++) dist[i]=INF,g[i].clear();
	for(int i=0;i<vec.size();i++) g[vec[i][1]].pb(mp(vec[i][2],vec[i][0]));
	int ans=0,cnt=0;
	priority_queue <pii > pq;
	dist[1]=0;
	pq.push(mp(0,1));
	while(pq.size())
	{
		int u=pq.top().se;
		pq.pop();
		if(dist[u]==-1) continue;
		cnt++,ans+=dist[u],dist[u]=-1;
		for(int i=0;i<g[u].size();i++) 
		{
			int v=g[u][i].fi,w=g[u][i].se;
			if(w<dist[v]) dist[v]=w,pq.push(mp(-dist[v],v));
		}
	}
	if(cnt<lim+1) ans=INF;
	return ans;
}
int n,m;
int U[500005],V[500005],W[500005]; 
void solve()
{
	cin>>n>>m;
	int idx=-1;
	vector <array<int,3> > vec;
	
	for(int i=1;i<=m;i++) 
	{
		cin>>U[i]>>V[i]>>W[i];
		if(U[i]<V[i]) vec.pb({W[i],U[i],V[i]});
		else idx=i;
	}
	int ans=calc(n,vec,n-1);
	if(V[idx]!=1)
	{
		vec.clear();
		int x=V[idx],y=U[idx];
//		cout<<"... "<<x<<" "<<y<<"\n";
		for(int i=1;i<=m;i++) if(V[i]!=x)
		{
			vec.pb({W[i],(U[i]==x?y:U[i]),V[i]});
//			cout<<"... "<<W[i]<<" "<<(U[i]==x?y:U[i])<<" "<<V[i]<<"\n";
		}
		ans=min(ans,calc(n,vec,n-2)+W[idx]);
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}