#include <stdio.h>

#define MOC 1000000000
int h[305][305];

int main(){
    int z,n,m,i,j,k,l;

    scanf("%d",&z);
    while(z--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                h[i][j]=MOC;
           for (i=1;i<=n;i++) h[i][i]=0;
        for(i=0;i<m;i++){
            scanf("%d%d%d",&j,&k,&l);
            h[j][k]=l;
            h[k][j]=l;
        }
                for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                    if(h[i][k]+h[k][j]<h[i][j]) h[i][j]=h[i][k]+h[k][j];
        l=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(h[i][j]>l) l=h[i][j];
        if(l==MOC) printf("Bez spojeni neni veleni!\n");
        else printf("Nejvetsi vzdalenost je %d.\n",l);
    }
 return 0;
}