#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 B(x,y) a[(x)<(y)?(x):(y)][(x)<(y)?(y):(x)]
#define A(x,y) B((x)%J,(y)%J)

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);
		for (ai=0;ai<J;ai++)
			memset(a[ai],0,J*sizeof(int));
		for(i=0;i<S;i++)
		{
			scanf("%d%d%d",&i1,&i2,&l);
			A(i1-1,i2-1)=l+1;
		}
		for (big=1;big<=J-1;big++)
			for (base=0;base<J;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)-2+1;
					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 (ai==bi)
					continue;
				if (!A(ai,bi)) {
					puts("Bez spojeni neni veleni!");
					goto out;
					}
				if (!best || A(ai,bi)>best)
					best=A(ai,bi);
				}
		printf("Nejvetsi vzdalenost je %d.\n",best-1);
out:
		}
	return(0);
}