var t,n,m,i,j,k,tt,pt,l,head,tail:longint; a,d:array[0..200]of longint; p,pre,c:array[1..20010]of longint;
    v:array[1..200]of boolean; q:array[1..5000]of longint;
begin
assign(input,'hardest.in'); assign(output,'hardest.out'); reset(input); rewrite(output);
 readln(t);
 for tt:=1 to t do begin
  readln(n,m); pt:=0; fillchar(p,sizeof(p),0); fillchar(d,sizeof(d),$3f);
  d[1]:=0; v[1]:=true; fillchar(pre,sizeof(pre),0);
  for i:=1 to m do
   begin
    readln(j,k,l);
    inc(pt); p[pt]:=j; pre[pt]:=a[k]; a[k]:=pt; c[pt]:=l;
    inc(pt); p[pt]:=k; pre[pt]:=a[j]; a[j]:=pt; c[pt]:=l;
   end; head:=1; tail:=1; q[1]:=1;
  while head<=tail do
   begin
    i:=a[q[head]];
    while i<>0 do
     begin
      if d[p[i]]>d[q[head]]+c[i] then
       begin
        d[p[i]]:=d[q[head]]+c[i];
        if not v[p[i]] then begin inc(tail); q[tail]:=p[i]; v[p[i]]:=true; end;
       end;
      i:=pre[i];
     end;
    v[q[head]]:=false; inc(head);
   end;
   if d[n]<>d[0] then writeln(d[n]) else writeln(-1);
  end;
close(input); close(output); 
end.