program Spojka;

const max=400;
      inf=1000000000;

var z, J, S, i: integer;
    d:	array[1..max, 1..max] of integer;
    a,b,c:	integer;
    p, k, l:	integer;
    nej: integer;
begin
  readln(z);
  while z>0 do
  begin
    z:=z-1;
    
    readln(J, S);
    
    for i:=1 to J do
      for k:=1 to J do
        if i<>k then d[i,k]:=inf else d[i,k]:=0;
    
    for i:=1 to S do
    begin
      readln(a,b,c);
      d[a,b]:=c; d[b,a]:=c;
    end;
    
    { vypocet }
    for p:=1 to J do
      for k:=1 to J do
        for l:=1 to J do
	  if d[p,k] > d[p,l]+d[l,k] then
	    d[p,k]:=d[p,l]+d[l,k];

    nej:=0;
    for p:=1 to J do
      for k:=1 to J do
        if d[p,k]>nej then nej:=d[p,k];

    if nej=inf then writeln('Bez spojeni neni veleni!') else
    writeln('Nejvetsi vzdalenost je ', nej,'.');
  end;
end.