program Spojka(input,output);

const MAXI=MAXINT;
var zadani, PocetZadani : integer;
    Matice,Matice1 : Array [1..300,1..300] of integer;
    Mist,Spojnic : integer;
    i,j : integer;
    m1,m2,v : integer;
    ch:boolean;
    oldm,max:integer;
 function f(a,b:integer):integer;
 begin
     if (a=MAXI) or (b=MAXI) then f:=MAXI
         else f:=a+b;
  end;     
  function Min(r,s:integer):integer;
    var nm,pom,x: integer;
    begin
      nm:=f(Matice1[r,1],Matice[1,s]);
      for x:=2 to Mist do
      begin
        pom:=f(Matice1[r,x],Matice[x,s]);
        if nm>pom then nm:=pom;
      end;	
    Min:=nm;  
    end;
      
    
begin
  ReadLn(PocetZadani);
  
  for zadani:=1 to PocetZadani do begin
    ReadLn(Mist,Spojnic);
    for i:=1 to Mist do for j:=1 to Mist 
      do Matice[i,j]:=MAXI;
    for i:=1 to Mist do	Matice[i,i]:=0;

    for i:=1 to Spojnic do begin
      readLn(m1,m2,v);
      matice[m1,m2]:=v;
      matice[m2,m1]:=v;
    end;
    Matice1:=Matice;
    ch:=true;
while (ch) do  
begin
    ch:=false;
    for i:=1 to Mist do 
      for j:=1 to Mist do 
	 begin
	    oldm:=Min(i,j);
{WriteLn("Min(",i,",",j,")=",oldm,"M1=",Matice1[i,j]);}
	    if Matice1[i,j]>oldm then 
	    begin
		ch:=true;
		Matice1[i,j]:=oldm;
	    end;
	end;
end;
    max:=0;
    for i:=1 to Mist do 
      for j:=1 to Mist do if max<Matice1[i,j] then max:=Matice1[i,j];
      
    if max=MAXI then WriteLn("Bez spojeni neni veleni!")
	else Writeln("Nejvetsi vzdalenost je ",max:0);
    end;

end.