#include <stdio.h>
#include <stdlib.h>

int main()
{
   int *sem,*zpet,*bodkud,*bkam,*bkolik,*zasob,
   czas,vbus,vst,N,i,maxprice,price,kdesem;
   
   scanf("%d\n",&N);
   for(;N>0;N--)
   {
      	scanf("%d %d\n",&vst,&vbus);
        bodkud=(int*)malloc(vbus*sizeof(int));
        bkam=(int*)malloc(vbus*sizeof(int));
        bkolik=(int*)malloc(vbus*sizeof(int));
        
        maxprice=0;
        for(i=0;i<vbus;i++)
        {
        	scanf("%d %d %d\n",bodkud+i,bkam+i,bkolik+i);
                if(maxprice<bkolik[i])maxprice=bkolik[i];
        }
        
        sem=(int*)malloc(vst*sizeof(int));
        zpet=(int*)malloc(vst*sizeof(int));
        for(i=0;i<vst;i++)
        	zpet[i]=(sem[i]=maxprice*vst);
        zasob=(int*)malloc(vst*sizeof(int));
        
        
        czas=1;
        *zasob=1;
        zpet[0]=(sem[0]=0);
        
        while(czas>0)
        {
        	kdesem=*zasob;
                zasob--;czas--;
                for(i=0;i<vbus;i++)
                   if(bodkud[i]==kdesem&&bkam[i]!=1&&
                   sem[bkam[i]-1]>sem[bodkud[i]-1]+bkolik[i])
                   {  	
                        zasob++;czas++;
                        *zasob=bkam[i];
                        sem[bkam[i]-1]=sem[bodkud[i]-1]+bkolik[i];
                   }
        }
        zasob++;
        
        czas=1;
        *zasob=1;
        
        while(czas>0)
        {
        	kdesem=*zasob;
                zasob--;czas--;
                for(i=0;i<vbus;i++)
                   if(bkam[i]==kdesem&&bodkud[i]!=1&&
                   zpet[bodkud[i]-1]>zpet[bkam[i]-1]+bkolik[i])
                   {  	
                        zasob++;czas++;
                        *zasob=bodkud[i];
                        zpet[bodkud[i]-1]=zpet[bkam[i]-1]+bkolik[i];
                   }
        }                
        
        zasob++;
        free(zasob);
        price=0;
        for(i=0;i<vst;i++)
        {  	price+=sem[i];
                price+=zpet[i];
        }
        printf("%d\n",price);
        free(bkam);free(bodkud);free(bkolik);
        free(sem);free(zpet);
   }
   
   return 0;
}
   
