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

#define MAX 300
#define NMAX INT_MAX

int J;
int l[300][300];
int nc[MAX][MAX];

void init(void){
  int i,j;
  for (i=0;i<J;i++){
    for (j=0;j<J;j++){
      if (i==j){
	l[i][j]=0;
      }else{
        l[i][j]=NMAX;
      }
    }
  }
}

void p(void){
  int i,j;
  return;
  for (i=0;i<J;i++){
    for (j=0;j<J;j++){
      printf("%d ", nc[i][j]);
    }
    printf("\n");
  }
}

void computepaths(void){
  int i,j;
  int k,q;
  while(q){
    q=0;
    p();
  for (i=0;i<J;i++){
    for (j=0;j<i;j++){
      for (k=0;k<J;k++){
	if ((k==i) || (j==k)) continue;
	if ((nc[i][k]==NMAX) || (nc[j][k]==NMAX)) continue;
	if (nc[i][k]+nc[j][k]<nc[i][j]){
	  nc[i][j]=nc[i][k]+nc[j][k];
	  nc[j][i]=nc[i][k]+nc[j][k];
	  q=1;
	}
      }
    }
  }
  }
}

void initpaths(void){
  int i,j;
  for (i=0;i<J;i++)
    for (j=0;j<J;j++){
      nc[i][j]=l[i][j];
    }
}

void result(void){
  int i,j;
  int max;
  max=0;
  for (i=0;i<J;i++){
    for (j=0;j<J;j++){
      if (nc[i][j]==NMAX){
	printf("Bez spojeni neni veleni!\n");
	return;
      }
      max= ( (max<nc[i][j]) ? nc[i][j] : max);
    }
  }
  if (max==NMAX){
    printf("Bez spojeni neni veleni!\n");
  }else{
    printf("Nejvetsi vzdalenost je %d.\n",max);
  }
}

int main(void){
  char LINE[1000];
  int n,i;
  int S,a,b,j,c;
  fgets(LINE,999,stdin);
  n=atoi(LINE);
  for (i=0;i<n;i++){
    fgets(LINE,999,stdin);
    sscanf(LINE,"%d %d",&J, &S);
    init();
    for (j=0;j<S;j++){
      fgets(LINE,999,stdin);
      sscanf(LINE,"%d %d %d",&a,&b,&c);
      a--;b--;
      l[a][b]=c;
      l[b][a]=c;
    }
    initpaths();
    computepaths();
    result();
  }
  return 0;
}