#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=1000010,inf=1000000000;long long ans;  int e,to[maxn],next[maxn],begin[maxn],w[maxn];  int e1,to1[maxn],next1[maxn],begin1[maxn],w1[maxn];  int d[maxn],p[maxn],q[maxn*50];  int m,n,f,l;  void add(int x,int y,int z){       to[++e]=y;       next[e]=begin[x];       begin[x]=e;       w[e]=z;            }  void add1(int x,int y,int z){       to1[++e1]=y;       next1[e1]=begin1[x];       begin1[x]=e1;       w1[e1]=z;            } int main(){	int i,j,k,m,n;	int t;	scanf("%d",&t);	while(t--){	    int i,j,k,x,y,z;          scanf("%d%d",&n,&m);       	e=0;e1=0;       	for(i=1;i<=n;i++){begin[i]=0;begin1[i]=0;}        	for(i=1;i<=m;i++){          scanf("%d%d%d",&x,&y,&z);                            add(x,y,z);          add1(y,x,z);          }		for(i=1;i<=n;i++){		    d[i]=inf;		    p[i]=0;		}		f=0;l=1;          d[1]=0;q[1]=1;p[1]=1;                  while(f
         
          d[k]+w[i]){                      d[to[i]]=d[k]+w[i];                      if(!p[to[i]]){                          q[++l]=to[i];                          p[to[i]]=1;                      }                                         }                        }                  ans=0;          for(i=1;i<=n;i++)ans+=d[i];                    for(i=1;i<=n;i++){              d[i]=inf;              p[i]=0;          }              f=0;l=1;          d[1]=0;q[1]=1;p[1]=1;                  while(f
          
           d[k]+w1[i]){                      d[to1[i]]=d[k]+w1[i];                      if(!p[to1[i]]){                          q[++l]=to1[i];                          p[to1[i]]=1;                      }                                         }                        }                  for(i=1;i<=n;i++)ans+=d[i];          printf("%I64d\n",ans);          	}	return 0;}