#include<bits/stdc++.h>
#define int long long
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

void solve();
int tt=0,flag=0;
int t = 1;
signed main() {
    fast
    
    cin >> t;
    while (t--) solve();
}

const int maxn=500010;
int n,m,inf=1e18,id=0;
struct A{int x,y,z;
};
A e[maxn];
int v[maxn];
bool v2[maxn];
int d[maxn];
int f[maxn];
vector<int>w[maxn];
int root=0;
void add(int x,int y,int z)
{
	e[++id]={x,y,z};
}
void dfs(int x)
{
	for(int i=0;i<w[x].size();i++)
	{
		if(v[w[x][i]])continue;
		v[w[x][i]]=v[x];
		dfs(w[x][i]);
	}
}
void ch2(int x)
{
	if(!v2[f[x]])
	{
		v2[f[x]]=1;
		ch2(f[x]);
	}
}
int ch()
{
    int ans=0;
	for(int i=1;i<=n;i++)
	{
		d[i]=inf;
		f[i]=0;
		v[i]=0;
		v2[i]=0;
		w[i].clear();
	}
	d[1]=0;
	for(int i=1;i<=m;i++)
	{
		if(e[i].y==1)continue;
		if(e[i].z<d[e[i].y])
		{
			f[e[i].y]=e[i].x;
			d[e[i].y]=e[i].z;
		}
	}
	int s=0;
	for(int i=1;i<=n;i++)
	{
		if(f[i]==0)continue;
		w[f[i]].push_back(i);
		ans+=d[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(!v[i])
		{
			s++;
			v[i]=s;
			dfs(i);
		}
	}
	if(s==1)return ans;
	ch2(root);
	s=inf;
	for(int i=1;i<=m;i++)
	{
		if(v2[e[i].y]&&v[e[i].x]!=v[e[i].y])
		{
			s=min(s,e[i].z-d[e[i].y]);
		}
	}

	return ans+s;
	
}
void solve() 
{
    id=0;
    tt++;
    root=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int x,y,z;
    	cin>>x>>y>>z;
    	if(flag&&tt==313)cout<<x<<"!!!"<<y<<"!!"<<z<<"\n";
    	if(t==50000&&tt==1&&x==1&&y==3)flag=1;
    	if(y<x)root=y;
    	add(x,y,z);
	}
	if(!flag)cout<<ch()<<"\n";
}
/*
1
4 5
2 3 39917807
1 2 830477742
3 4 670700294
1 4 894960672
3 2 142909800
*/