#include<stdio.h>

int pocetZadani,s,jedn,tjedn;
int matice[302][302];
int pole[301][2], indexpole;
int max=0, aktmax=0;

void Res()
{
  int i,j;
  for(i=0; i<=301; i++)
    for(j=0; j<=301; j++)
      matice[i][j]=0;
}

void Res2()
{
  int i;
  indexpole=0;
  for(i=0; i<=301; i++)
  {
    pole[i][0]=0;
    pole[i][1]=0;
  }
}

void Nacti()
{
  int j1,j2,delka,i;
  scanf("%d %d",&jedn,&s);
  for(i=0; i<s; i++)
  {
    scanf("%d %d %d",&j1,&j2,&delka);
    matice[j1][j2]=delka;
    matice[j2][j1]=delka;
  }
}

int Projdi(int i,int j)
{
  int pocetj = 0;
  int lmax,li;
  int lj=1;
  Res2();
  li = i;
  while(li!=0)
  {
    pocetj++;
    lj=1;
    pole[i][1]=1;
    while(lj<=j)
    {  
/*      printf("lj %d, matice[i][lj] %d, pole[lj] %d %d\n",lj,matice[i][lj],pole[lj][0],pole[lj][1]);*/
      if((matice[i][lj]!=0)&&( ((pole[lj][1]==2)&&(pole[lj][0]>(pole[i][0]+matice[i][lj]))) || (pole[lj][1]==0) ))
      {
        pole[lj][0]=pole[i][0]+matice[i][lj];
        pole[lj][1]=2;
/*        printf("%d %d\n",i,lj);*/
      }
      lj++;
      while(matice[i][lj]==0)lj++;
    }
    lmax=90000;
    li = 0;
    for(i=1;i<=j;i++)
      if((pole[i][1]==2)&&(pole[i][0]<lmax)){ lmax = pole[i][0]; li = i; }
/*    printf("%d %d\n",lmax,li);*/
    i = li;
  }
  lmax=0;
  for(i=1; i<=j; i++)
  {
    if (pole[i][1]==0)return 0;
    else
    if (pole[i][0]>lmax)lmax=pole[i][0];
  }
  return lmax;
}

int main()
{
  int i,p;
  Res2();
  scanf("%d",&pocetZadani);
  for(p=1; p<=pocetZadani;p++)
  {
    Res();
    Nacti();
    max = 0;
    i=1;
    while(i<=jedn)
    {
      tjedn = jedn;
      aktmax=Projdi(i,jedn);
      jedn = tjedn;
/*      printf("%d %d\n",aktmax,jedn);*/
/*      printf("%d\n", aktmax);*/
      if (aktmax==0) 
      { 
        printf("Bez spojeni neni veleni!\n"); 
        i=jedn; 
      }
      else 
      if (aktmax>max) max = aktmax;
      i++;
    }
    if (aktmax!=0) printf("Nejvetsi vzdalenost je %d.\n",max);
  }
  return 0;
}