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

#define DUNDEF 0xfffffff

#if 0
#define STRACE(msg) do { printf##msg; fflush(stdout); } while (0)
#else
#define STRACE(msg) (void)0
#endif

unsigned distz[500][500];
int ncitiez;

void test_city(int city)
{
    int i;
    unsigned gr_in[500];
    int gri_size;
    unsigned gr_out[500];
    unsigned cur_cnt[500];
    int gro_size;
    for (gri_size = 0, i = 0; i < ncitiez; i++) {
	if (distz[city][i] < DUNDEF) {
	    gr_in[gri_size++] = i;
	    STRACE(("init: added %d to in\n", i));
	}
    }
    while (gri_size > 0) {
	STRACE(("running loop with gri %d\n", gri_size));
	bzero(cur_cnt, ncitiez*sizeof(cur_cnt[0]));
	for (gro_size = 0, i = 0; i < gri_size; i++) {
	    int src = gr_in[i];
	    int dst;
	    unsigned srcdist = distz[city][src];
	    for (dst = city+1; dst < ncitiez; dst++) {
		if (distz[src][dst] >= DUNDEF)
		    continue;
		if (distz[city][dst] > srcdist+distz[src][dst]) {
		    distz[dst][city] = distz[city][dst] = srcdist+distz[src][dst];
		    STRACE(("current dist %d %d: %d\n", city, dst, distz[dst][city]));
		    if (cur_cnt[dst]++ == 0)
			gr_out[gro_size++] = dst;
		}
	    }
	}
	gri_size = gro_size;
	memcpy(gr_in, gr_out, gri_size*sizeof(gr_in[0]));
    }
    STRACE(("city %d: finish\n", city));
}

int main(void)
{
    int nnnn;
    scanf("%d", &nnnn);
    while (nnnn--) {
	int i;
	int ndistz;
	unsigned max;
	scanf("%d %d", &ncitiez, &ndistz);
	memset(distz, 0xff, sizeof(distz));
	for (i = 0; i < ncitiez; i++)
	    distz[i][i] = 0;
	for (i = 0; i < ndistz; i++) {
	    unsigned src, dst, dist;
	    scanf("%d %d %d", &src, &dst, &dist);
	    src--; dst--;
	    distz[src][dst] = dist;
	    distz[dst][src] = dist;
	}
	test_city(0);
	for (i = 0; i < ncitiez; i++) {
	    if (distz[0][i] >= DUNDEF) {
		STRACE(("scheise %d failed\n", i));
		goto kein_connect;
	    }
	}
	for (i = 1; i < ncitiez; i++) {
	    test_city(i);
	}
	max = 0;
	for (i = 0; i < ncitiez; i++) {
	    int j;
	    for (j = i+1; j < ncitiez; j++) {
		if (distz[i][j] > max)
		    max = distz[i][j];
	    }
	}
	printf("Nejvetsi vzdalenost je %d.\n", max);
	continue;
kein_connect:
	printf("Bez spojeni neni veleni!\n");
    }
    return 0;
}