#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <math.h>


#define LENGTH(x) (sizeof(x)/sizeof(*(x)))
#define CLEAR(x) memset(x,0,sizeof(x))

int N,Ni;
int J,S;

int a[300][300];
int i1,i2,l;

#define A(x,y) a[(x)<(y)?(x):(y)][(x)<(y)?(y):(x)]

int main(void)
{
int base,big,find,best,now;
int i,ai,bi;

	scanf("%d",&N);
	for (Ni=0;Ni<N;Ni++) {
		scanf("%d%d",&J,&S);
		CLEAR(a);
		for(i=0;i<S;i++)
		{
			scanf("%d%d%d",&i1,&i2,&l);
			A(i1-1,i2-1)=l;
		}
		for (big=1;big<J-1;big++) {
			for (base=0;base+big<=J-1;base++)
				best=0;
				for (find=0;find<J;find++) {
					if (!(A(base,find) && A(find,base+big)))
						continue;
					now=A(base,find)+A(find,base+big);
					if (!best || now<best)
						best=now;
					}
				if (!A(base,base+big) || (best && best<A(base,base+big)))
					A(base,base+big)=best;
			}
		best=0;
		for (ai=0;ai<J;ai++)
			for (bi=0;bi<ai;bi++) {
				if (!best || A(ai,bi)<best)
					best=A(ai,bi);
				}
		if (!best)
			puts("Bez spojeni neni veleni!");
		else printf("Nejvetsi vzdalenost je 7.\n");
		}
	return(0);
}