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

#define INF 999999

int matice[305][305];

int n;

void nasob(void)
{
  int x, y, i;
  for (x=0; x<n; x++)
    for (y=0; y<n; y++) {
      for (i=0; i<n; i++) {
	if (matice[x][y] > (matice[x][i] + matice[i][y]))
	  matice[x][y] = matice[x][i] + matice[i][y];
      }
    }
}

int main(void)
{
  int pocet, c_ulohy;
  scanf("%d\n", &pocet);
  for (c_ulohy =0; c_ulohy < pocet; c_ulohy++) {
    int i,j,k;
    scanf("%d %d", &n, &k);
    for (i=0; i<n; i++)
      for (j=0; j<n; j++) {
	matice[i][j] = INF;
      }
    for (i=0; i<k; i++) {
      int z, d, cena;
      scanf("%d %d %d\n", &z, &d, &cena);
      matice[z-1][d-1] = cena;
      matice[d-1][z-1] = cena;
    }
    for (i=0; i<n; i++)
      matice[i][i] = 0;
    for (i=0; i<n; i++)
      nasob();
    {
      int max = 0;
      for (i=0; i<n; i++)
	for (j=0; j<n; j++) {
	  /*	  printf("%d ", matice[i][j] );*/
	  if (matice[i][j] > max)
	    max = matice[i][j];
	}
      if (max == INF)
	printf("Bez spojeni neni veleni!\n");
      else
	printf("Nejvetsi vzdalenost je %d.\n", max);
    }
  }
  return 0;
}