#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define max(a,b) a>b?a:b
#define min(a,b) a>b?b:a
int t,n,m,p,q,w,a[201][201],minx=999999999;
int i,j,t,z,x,c,k,l;
int main()
{
	//FILE *fin=fopen("hardest.in","r"),*fout=fopen("hardest.out","w");
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	scanf("%d",&t);
	memset(a,1,sizeof(a));
	for(i=0;i<t;i++)
	{
		scanf("%d %d",&n,&m);
		for(j=0;j<=n;j++)
			a[j][j]=0;
		for(j=0;j<m;j++)
		{
			scanf("%d %d %d",&p,&q,&w);
			if(a[p][q]>w)
				a[p][q]=a[q][p]=w;
		}
		for(c=0;c<n;c++)
			for(z=0;z<n;z++)
				for(x=0;x<n;x++)
					a[z][x]=min(a[z][x],a[z][c]+a[x][c]);
		for(j=1;j<=n;j++)
		{
			for(k=j;k<=n;k++)
			{
				if(a[j][k]<minx&&a[j][k]!=0)
					minx=a[j][k];
			}
		}
		printf("%d\n",minx);
	}
	return 0;
}