> #include<cstdio>//十足的水题
> #include<cstdlib>
> #include<cstring>
> #include<cmath>
> #include<string>
> #include<iostream>
> #include<queue>
> #include<iomanip>
> #include<algorithm>
> using namespace std;
> const int N=1000010;
> 
> struct edge
> {
> 	int v,nx,w;
> }ee[N],e[N];
> int n,m,headd[N],head[N],id;
> int l,r,q[2*N],d[N];
> bool vis[N];
> 
> void add(int u,int v,int w)
> {
> 	id++;
> 	e[id].v=v;e[id].w=w;e[id].nx=head[u];head[u]=id;
> 	ee[id].v=u;ee[id].w=w;ee[id].nx=headd[v];headd[v]=id;
> }
> 
> long long spfaa()
> {
> 	int i,j,u,v;
> 	memset(d,0x7f,sizeof(d));
> 	memset(vis,false,sizeof(vis));
> 	l=1;r=1;q[1]=1;d[1]=0;vis[1]=true;
> 	while(l<=r)
> 	{
> 		u=q[l];l++;
> 		vis[u]=false;
> 		for(i=head[u];i!=-1;i=e[i].nx)
> 		{
> 			v=e[i].v;
> 			if(d[u]+e[i].w<d[v])
> 			{
> 				d[v]=d[u]+e[i].w;
> 				if(!vis[v])
> 				{
> 					r++;q[r]=v;
> 				}
> 			}
> 		}
> 	}
> 	long long res=0;
> 	for(i=2;i<=n;i++) res+=d[i];
> 	return res;
> }
> 
> long long spfab()
> {
> 	int i,j,u,v;
> 	memset(d,0x7f,sizeof(d));
> 	memset(vis,false,sizeof(vis));
> 	l=1;r=1;q[1]=1;d[1]=0;vis[1]=true;
> 	while(l<=r)
> 	{
> 		u=q[l];l++;
> 		vis[u]=false;
> 		for(i=headd[u];i!=-1;i=ee[i].nx)
> 		{
> 			v=ee[i].v;
> 			if(d[u]+ee[i].w<d[v])
> 			{
> 				d[v]=d[u]+ee[i].w;
> 				if(!vis[v])
> 				{
> 					r++;q[r]=v;
> 				}
> 			}
> 		}
> 	}
> 	long long res=0;
> 	for(i=2;i<=n;i++) res+=d[i];
> 	return res;
> }
> 
> int main()
> {
> 	int i,j,cas,a,b,c;
> 	scanf("%d",&cas);
> 	while(cas--)
> 	{
> 		scanf("%d%d",&n,&m);
> 		id=0;
> 		memset(head,-1,sizeof(head));
> 		memset(headd,-1,sizeof(headd));
> 		for(i=1;i<=m;i++)
> 		{
> 			scanf("%d%d%d",&a,&b,&c);
> 			add(a,b,c);
> 		}
> 		printf("%I64d\n",spfaa()+spfab());
> 	}
> 	return 0;
> }