program cogs1254;
type nod=record
        y,n,d:longint;
end;
var
   x,t,i,j,tt,z,n,m,h,y,dd,u,v,p:longint;
   bb:array[0..202]of boolean;
   b:array[0..21000]of nod;
   s,q,d:array[0..202]of longint;
procedure init;
begin
     assign(input,'hardest.in');reset(input);
     assign(output,'hardest.out');rewrite(output);
end;
procedure add(p,q,dd:longint);
begin
     inc(t);
     b[t].y:=q;b[t].d:=dd;
     b[t].n:=s[p];s[p]:=t;
end;
procedure main;
begin
     readln(z);
     for tt:=1 to z do
     begin
          readln(n,m);
          t:=0;
          fillchar(s,sizeof(s),0);
          for i:=1 to m do
          begin
               readln(u,v,dd);
               add(u,v,dd);
               add(v,u,dd);
          end;
          fillchar(bb,sizeof(bb),1);
          bb[1]:=false;
          fillchar(d,sizeof(d),$0f);
          d[1]:=0;
          h:=0;t:=1;q[1]:=1;
          while h<>t do
          begin
               inc(h);if h>200 then h:=1;
               x:=q[h];p:=s[x];
               while p<>0 do
               begin
                    y:=b[p].y;
                    if d[y]>d[x]+b[p].d then
                    begin
                         d[y]:=d[x]+b[p].d;
                         if bb[y] then
                         begin
                              inc(t);if t>200 then t:=1;
                              q[t]:=y;bb[y]:=false;
                         end;
                    end;
                    p:=b[p].n;
               end;
          bb[x]:=true;
          end;
          if d[n]=d[0] then writeln(-1) else writeln(d[n]);
     end;
end;
begin
     init;
     main;
end.//complete by chouyi20140919