#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define int long long
using namespace std;

const int maxn = 210000;
const int inf = 1e9;

int n,m;
vector< pair<int,int> >E[maxn];

signed main()
{
	ios_base::sync_with_stdio(false);
	
	int Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			vector< pair<int,int> >_;
			E[i].swap(_);
		}
		int spu,spv,spw;
		for(int i=1;i<=m;i++)
		{
			int u,v,w; cin>>u>>v>>w;
			if(u<v) E[v].emplace_back(u,w);
			else spu=u,spv=v,spw=w;
		}
		
		vector<int>go(n+5),goc(n+5);
		int ans=0;
		go[1]=0,goc[1]=0;
		for(int i=2;i<=n;i++)
		{
			int mn=inf;
			for(auto [j,c]:E[i]) 
			{
				if(mn>c)
					mn=c,go[i]=j,goc[i]=c;
			}
			ans+=mn;
		}
		
		if(spv!=1)
		{
			int sum= ans-goc[spv]+spw;
			
			vector<int>V,vis(n+5);
			for(int i=spu;i;i=go[i])
			{
				V.push_back(i);
				vis[i]=1;
				if(i==spv) break;
			}
			int temp=0;
			if(V.back()==spv)
			{
				temp=inf;
				for(auto i:V) if(i!=spv)
				{
					for(auto [j,c]:E[i]) if(j!=go[i] && vis[j]==0)
					{
						temp=min(temp, c-goc[i]);
					}
				}
			}
			
			ans=min(ans, sum+temp );
		}
		cout<<ans<<'\n';
	}
	
	return 0;
}