var
t,n,m,q,i,j,a,b,k:integer;
f:array[0..201,0..201]of integer;
begin
assign(input,'hardest.in');reset(input);
assign(output,'hardest.out');rewrite(output);
read(t);
for q:=1 to t do
 begin
  read(n,m);
  //+++++++++++++++++++++++++++++
  for i:=1 to n do
   for j:=1 to n do
    if i=j then f[i,j]:=0
    else f[i,j]:=-1;
  //+++++++++++++++++++++++++++++
  for i:=1 to m do
   begin
    read(a,b,k);
    if (f[a,b]>k)or(f[a,b]=-1) then
     begin  f[a,b]:=k;f[b,a]:=k;end;
   end;
  //+++++++++++++++++++++++++++++
  for k:=1 to n do
   for i:=1 to n do
    if (i<>k)and(f[i,k]>-1) then
     for j:=1 to n do
      if ((f[i,j]=-1)and(f[j,k]>-1))or((i<>j)and(j<>k)and(f[i,j]>-1)and(f[j,k]>-1)and(f[i,k]+f[j,k]<f[i,j]))then
       f[i,j]:=f[i,k]+f[j,k];f[j,i]:=f[i,j];
  //+++++++++++++++++++++++++++++
   writeln(f[1,n]);
 end;
close(input);close(output);
end.