var f:array[0..200]of longint;
    v:array[1..200]of boolean;
    a:array[1..200,1..200]of longint;
    b:array[1..200,0..10000]of longint;
    p:array[1..20000]of longint;
    i,k,x,now,y,z,n,m,t,head,tail:longint;

begin
 assign(input,'hardest.in');reset(input);
 assign(output,'hardest.out');rewrite(output);
 readln(t);
 for k:=1 to t do
  begin
   readln(n,m);
   fillchar(b,sizeof(b),0);
   fillchar(a,sizeof(a),0);
   for i:=1 to m do
    begin
     readln(x,y,z);
     inc(b[x,0]);b[x,b[x,0]]:=y;a[x,y]:=z;
     inc(b[y,0]);b[y,b[y,0]]:=x;a[y,x]:=z;
    end;
   fillchar(v,sizeof(v),false);
   fillchar(f,sizeof(f),$7f);
   p[1]:=1;f[1]:=0;head:=0;tail:=1;
   while head<>tail do
    begin
     inc(head);
     now:=p[head];v[now]:=false;
     for i:=1 to b[now,0]do
      begin
       x:=b[now,i];
       if f[x]>f[now]+a[x,now] then
        begin
         f[x]:=f[now]+a[x,now];
         if not(v[x])then
          begin inc(tail);p[tail]:=x;v[x]:=true;end;
        end;
      end;
    end;
   if f[n]<>f[0]then writeln(f[n])else writeln('-1');
  end;
 close(output);
end.