#include <stdio.h>
int m[300][300];
int s,j,a=0;

int mat(int s1,int s2){
if(s1<=s2) return m[s1][s2];
else return m[s2][s1];
}

int  aktu(int s1,int s2,int c){
int s3,i,x;
if (s1==s2) return 0;
if (s1>s2){s3=s1;s1=s2;s2=s3;}
if (m[s1][s2]<=c && m[s1][s2]!=-1)  return 0;
/*printf("s1=%d s2=%d c=%d\n",s1,s2,c);*/
m[s1][s2]=c;
for (i=0;i<j;i++){
x=0; 
if (s1!=i && mat(i,s1)!=-1) x=aktu(s2,i,c+mat(i,s1));
if (!x && s2!=i && mat(i,s2)!=-1)  aktu(s1,i,c+mat(i,s2));
}a++;
return 1;
}

int main(void) {
int i,n;int max;
int ii,s1,s2,c;
int iii;
  
scanf("%d",&n);
  
for(i=0;i<n;i++) {
for (iii=0;iii<300;iii++) for(ii=0;ii<300;ii++) m[ii][iii]=-1;
scanf("%d%d",&j,&s);
for(ii=0;ii<s;ii++) {
scanf("%d%d%d",&s1,&s2,&c);
s1--;s2--;
aktu(s1,s2,c);
}
/*
for (iii=0;iii<j;iii++) {for(ii=0;ii<j;ii++) {
printf("%d ",m[iii][ii]);
}
printf("\n");
}
*/
max=0;
for (ii=0;ii<j;ii++) { for (iii=0;iii<ii;iii++) {
if (m[iii][ii]>max) max=m[iii][ii];
else if (m[iii][ii]==-1) {max=-1;break;}
}
if (max==-1) break;
}

if (max==-1) printf("Bez spojeni neni veleni!\n");
else printf("Nejvetsi vzdalenost je %d.\n", max);
}
/*printf("a=%d\n",a);*/
return 0;
}