var
    i,j,n,k,m,p,t,x,y:longint;
    f:array[0..200,0..200] of longint;
    begin
          assign(input,'hardest.in');
          reset(input);
          assign(output,'hardest.out');
          rewrite(output);
          read(p);
          for t:=1 to p do
          begin
               read(n,m);
               for i:= 1 to n do
               for j:= 1 to n do
               f[i,j]:=-1;
               for i:= 1 to m do
               begin
                    read(x,y);
                    read(f[x,y]);
                    f[y,x]:=f[x,y];
               end;
               for k:=1 to n do
               for i:=1 to n do
               for j:=1 to n do
               begin
                    if (f[i,j]>f[i,k]+f[k,j]) or (f[i,j]=-1)
                    and(f[i,k]<>-1) and(f[k,j]<>-1) then
                    f[i,j]:=f[i,k]+f[k,j];
               end;
               writeln(f[1,n]);
          end;
          close(input);
          close(output);
    end.