#include <stdio.h>
#include <limits.h>

#define MAX_INT 2000000000

int mat[301][301];
int poc;
int n;
int use[301];

void R(int v)
{ 
  int i;
  
  if (use[v] == 0) {
    use[v]=1;
    poc++;
    for (i=1;i<=n;i++)
      if (mat[v][i] != MAX_INT) R(i);
  }
}

int ma(int a,int b){ if (a<=b) return(a); else return(b); }

int main(void)
{
  int z,nz,m;
  int i,j,k,pom,vysl;

  scanf("%d", &nz);
  for (z=0;z<nz;z++) {
    scanf("%d%d", &n, &m);
    for (i=0;i<=n;i++)
      for (j=0;j<=n;j++)
        mat[i][j]=MAX_INT;
    for (k=0;k<m;k++) {
      scanf("%d%d%d", &i, &j, &pom);
      mat[i][j]=mat[j][i]=pom;
    }  
    for (i=0;i<=n;i++)
      use[i]=0;
    poc=0;  
    R(1); 
    if (poc != n) 
      printf("Bez spojeni neni veleni!\n");
    else {
      vysl=0;
      for (k=1;k<=n;k++)
        for (i=1;i<=n;i++)
	  for (j=1;j<=n;j++) 
	  { if (mat[i][k] != MAX_INT && mat[k][j] != MAX_INT)
              if (mat[i][k]+mat[k][j] < mat[i][j])
                mat[i][j]=mat[i][k]+mat[k][j];
	  }
       for (i=1;i<=n;i++) {
/*	       putchar('\n'); */
         for (j=1;j<=n;j++) {
           if (i!=j)		 
           if (mat[i][j] > vysl) vysl=mat[i][j];
/*	   printf("%d ", mat[i][j]);*/
	 }  
       }	 
       printf("Nejvetsi vzdalenost je %d.\n", vysl); 
    }  
    
  }
  return 0;
}