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

#define MAX (1 << 29)

int main(void)
{
	int zad;
	int i, j, k;
	int *D;
	int *D1;

	scanf("%d",&zad);

	D = malloc (300 * 300 * sizeof (int));
	D1 = malloc (300 * 300 * sizeof (int));

	if (! D || !D1)
		return 1;

	while (zad--) {
		int N;
		int num_spojnic;
		int max;

		scanf ("%d %d\n", &N, &num_spojnic);

		for (i = 0; i < N; i++)
				for (j = 0; j < N; j++)
						D[i * N +j] = MAX;

		for (i = 0; i < N; i++)
				D[i * N + i] = 0;

		for (i = 0; i < num_spojnic; i++) {
				int a, b, c;
				scanf ("%d %d %d", &a, &b, &c);

				a--;
				b--;
				D[a * N + b] = D[b * N + a] = c;
		}

		/* Solve (Res). */
		for (k = 0; k < N; k++) {
				int *temp;
				/*
				printf ("\n-------------------------------\n");
				*/
				for (i = 0; i < N; i++) {
						for (j = 0; j < i; j++) {
								int v1, v2;
								v1 = D[i * N + j];
								v2 = D[i * N + k] + D[k * N +j];
								/*
								printf ("at [%d, %d]: v1 = %d, v2 = %d\n",
												i, j, v1, v2);
								*/
								D1[i * N + j] = (v1 < v2) ? v1 : v2;
								D1[j * N + i] = D1[i * N + j];
						}
				}
				/* Swap the arrays. */
				temp = D;
				D = D1;
				D1 = temp;
		}

		/* Write output. */
		max = 0;
		for (i = 0; i < N; i++) {
				for (j = 0; j < N; j++) {
						if (D[i * N + j] == MAX) {
								printf ("Bez spojeni neni veleni!\n");
								goto out;
						}
						if (D[i * N + j] > max)
								max = D[i * N + j];
				}
		}

		printf ("Nejvetsi vzdalenost je %d.\n", max);

out:
		/*
		printf ("D = %p, D1 = %p\n", D, D1);
		free (D);
		free (D1);
		printf ("Went OK\n");
		*/
	} /* while - pro vsechna zadani. */

	return 0;
}