#include <iostream.h>
#include<stdio.h>
#define MAXINT 1000000000

int min(int a, int b) {
    if(a>b) return b;
    else return a;
}

void pracuj() {
    int J, S, i,j,k, a,b,c, MX;
    int D[301][301];
    cin>>J>>S;
//    cout<<"j:"<<J<<"s:"<<S<<'\n';
//    scanf("%d %d",&J, &S);
    for(i=0;i<=J;i++)
	for(j=1;j<=J;j++) 
	    D[i][j] = MAXINT;
	    
    for(i=0;i<=J;i++) D[i][i] =0;
	
    while(S) {
	cin>>a>>b>>c;
//	cout<<"a"<<a<<"b"<<b<<"c"<<c;
//	scanf("%d %d %d",&a,&b,&c);
	D[a][b] = c;
	D[b][a] = c;
	S--;
    }
    
    for(k=1; k<=J; k++) {
	MX = 0;
	for(i=1; i<=J; i++) {
	    for(j=1; j<=J; j++) {
		D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
		if( D[i][j] > MX) MX=D[i][j];
	    }
	}
    }
    if(MX==MAXINT) printf("Bez spojeni neni veleni!\n");
    else printf("Nejvetsi vzdalenost je %d.\n",MX);

}



int main(void) {
    int N;
//    scanf("%d",&N);
    cin>>N;
//    cout<<"zadani:"<<N<<'\n';
    while(N) {
    
	pracuj();
	
	N--;
    }
    return(0);
}