program hardest;
 var t,i,j,k,x,y,n,loop,m:longint;
     a:array[1..300,1..300]of longint;
  begin
   assign(input,'hardest.in');
   reset(input);
   assign(output,'hardest.out');
   rewrite(output);
   read(t);
   for loop:=1 to t do
    begin
     read(n,m);
     for i:=1 to n do 
      for j:=1 to n do
       a[i,j]:=100000;
     for i:=1 to n do
      a[i,i]:=0;
     for i:=1 to m do
      begin
       read(x,y,a[x,y]);
       a[y,x]:=a[x,y];
      end;
     for k:=1 to n do
      for i:=1 to n do
       for j:=1 to n do
        if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
     if a[1,n]<>100000then write(a[1,n]) else write(-1);
    end; 
   close(input);
   close(output);
  end.