#include <stdio.h>

void doit (void) {
int i,j,k,pom,pom2,A,B,mat[310][310],tmp;
scanf("%d %d",&A,&B);
for (k=0;k<A;k++) 
  for (i=0;i<A;i++) {
      mat[k][i]=0;
     } 

for (i=0;i<B;i++) {
    scanf("%d %d %d",&j,&k,&pom);
    mat[j-1][k-1]=pom;
    mat[k-1][j-1]=pom;
  }
for (k=0;k<A;k++) 
  for (i=0;i<A;i++) {
      if (mat[k][i]==0) mat[k][i]=0xfffffff;
//      printf("#%d#",mat[k][i]);
     } 
      
for (k=0;k<A;k++)
  for (i=0;i<A;i++)
    for(j=0;j<A;j++) {
      if (mat[i][j]>(mat[i][k]+mat[k][j])) mat[i][j]=mat[i][k]+mat[k][j];      
    } 
tmp=0;    
pom2=0;
for(i=0;i<A;i++) {
    pom=0;
    for(j=0;j<A;j++){
    if (mat[i][j]!=0xfffffff) pom=1;
    if ((tmp<mat[i][j])&&(mat[i][j]!=0xfffffff)) tmp=mat[i][j];
//    printf("#%d#",mat[i][j]);
  }
  if (pom==0) pom2=1;
//  printf("\n");
  
}
if (pom2==1) printf("Bez spojeni neni veleni!\n");
else printf("Nejvetsi vzdalenost je %d.\n",tmp-1);
}

int main (void) {
int a,b;
scanf("%d",&a);
for(b=0;b<a;b++) doit();
return 0;
}