#include"cstdio"
#include"queue"
#include"vector"
#include"cstring"
using namespace std;
const int MAXN=1000005;
const int INF=0x3fffffff;
typedef long long LL;
typedef pair<int,int> P;
struct Edge{
	int to,cost,next;
}es[2][MAXN];
int V,E;
int head[2][MAXN];
LL d[MAXN];
int Scan_d()
{
	char ch;
	int res=0;
	while(ch=getchar())
	{
		if(ch==' '||ch=='\n')
			return res;
		res*=10;
		res+=ch-'0';
	}
}
void add_edge(int u,int v,int cost,int type)
{
	es[type][E].to=v;
	es[type][E].cost=cost;
	es[type][E].next=head[type][u];
	head[type][u]=E;
}

LL dijkstra(int s,int type)
{
	for(int i=1;i<=V;i++)	d[i]=INF;
	
	priority_queue<P,vector<P>,greater<P> > que;
	d[s]=0,que.push(P(0,s));
	
	while(!que.empty())
	{
		P p=que.top();que.pop();
		int v=p.second;
		if(d[v]<p.first)	continue;
		for(int i=head[type][v];i!=-1;i=es[type][i].next)
		{
			Edge e=es[type][i];
			if(d[e.to]>d[v]+e.cost)
			{
				d[e.to]=d[v]+e.cost;
				que.push(P(d[e.to],e.to));
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=V;i++)
		ans+=d[i];
	return ans;
}

int main()
{
	
	int T;
	T=Scan_d();
	for(int cas=1;cas<=T;cas++)
	{		
		int P,Q;
		P=Scan_d(),Q=Scan_d();
		V=P,E=0;
		for(int i=1;i<=V;i++)	head[0][i]=head[1][i]=-1;
		for(int i=0;i<Q;i++)
		{
			int u,v,co;
			u=Scan_d(),v=Scan_d(),co=Scan_d();
			add_edge(u,v,co,0);
			add_edge(v,u,co,1);
			E++;	
		}
		
		LL res=0;
		res+=dijkstra(1,0);
		res+=dijkstra(1,1);
		printf("%I64d\n",res);
	
	}
	
    return 0;
}