var  a:array[0..300,0..300]of longint;q:Array[0..100000]of longint;
     d:array[0..300]of longint;v:array[0..300]of boolean;
     sb,x,y,z,t,i,h,r,m,n:longint;
begin
 assign(input,'hardest.in');assign(output,'hardest.out');
 reset(input);rewrite(output);
 readln(r);
 for sb:=1 to r do
  begin
   readln(n,m); fillchar(a,sizeof(a),0);
   for i:=1 to m do
    begin
     readln(x,y,z);a[x,y]:=z;a[y,x]:=z;
    end;
   h:=0;t:=1;fillchar(d,sizeof(d),127);fillchar(v,sizeof(v),0);
   q[1]:=1;v[1]:=true;d[1]:=0;
   while h<t do begin
    inc(h);for i:=1 to n do if a[q[h],i]>0 then
      if d[i]>d[q[h]]+a[q[h],i] then  begin
         d[i]:=d[q[h]]+a[q[h],i];
         if not v[i]then begin inc(t);q[t]:=i;v[i]:=true;end;
      end;
    v[q[h]]:=false;
   end;
  if d[n]>1000000 then writeln('-1') else writeln(d[n]);
 end;
 close(output);
end.