#include<cstdio>#include<cstring>#include<queue>#include<algorithm>const int maxn = 1000009;const int inf = 1<<30;#include<vector>struct node{	int v,w;	node(int v,int w):v(v),w(w){}	bool operator < (const node a)const	{		return w > a.w;	}};std::vector<node> eg[maxn];std::priority_queue<node> q;int n,m;int vis[maxn];int dis[maxn];int a[maxn],b[maxn],c[maxn];void DIJ(){	int i;	memset(vis,0,sizeof(vis));	for(i=0;i<=n;i++)		dis[i] = inf;	while(!q.empty())q.pop();	dis[1] = 0;	vis[1] = 0;	int size = eg[1].size();	for(i=0; i < size; i++)	{		q.push(node(eg[1][i].v,eg[1][i].w));		dis[eg[1][i].v] = eg[1][i].w;	}	while(!q.empty())	{		int u = q.top().v;		int w = q.top().w;		q.pop();		if(!vis[u])		{			vis[u] = 1;			size = eg[u].size();			for(i=0; i<size; i++)			{				int v = eg[u][i].v;				int w = eg[u][i].w;				if(!vis[v] && dis[u] + w < dis[v])				{					dis[v] = dis[u] + w;					q.push(node(v,dis[v]));				}			}		}	}	}void work(){	int i,sum = 0;	DIJ();	for(i=2; i<=n; i++)   sum += dis[i]; //printf("%d ",dis[i]);}	for(i=0; i<=n; i++) eg[i].clear();	for(i=0;i<m;i++)    eg[b[i]].push_back(node(a[i],c[i]));  //  printf("\n");	DIJ();	for(i=2; i <= n;i++) sum += dis[i]; //printf("%d ",dis[i]);}	printf("%d\n",sum);}void input(){	int i;	scanf("%d%d",&n,&m);	for(i=0 ;i < m; i++)  scanf("%d%d%d",&a[i],&b[i],&c[i]);	for(i=0;i<=n;i++)     eg[i].clear();	for(i=0;i<m;i++)      eg[a[i]].push_back(node(b[i],c[i]));}int main(){	int t;	scanf("%d",&t);	while(t--)	{		input();				work();	}	return 0;}/*32 21 2 132 1 334 61 2 102 1 601 3 203 4 102 4 54 1 502 21 2 132 1 33  */