var
 head,d:array[0..210]of longint;
 v,w,next:array[0..21000]of longint;
 vis:array[0..210]of boolean;
 q:array[0..100100]of longint;
 i,j,k,l,m,n,cnt,p,t:longint;
 
procedure addedge(x,y,z:longint);
 begin
  inc(cnt);
  w[cnt]:=y;v[cnt]:=z;
  next[cnt]:=head[x];
  head[x]:=cnt;
 end;
 
procedure init;
 var
  x,y,z:longint;
 begin
  fillchar(v,sizeof(v),0);
  fillchar(w,sizeof(w),0);
  fillchar(head,sizeof(head),0);
  fillchar(next,sizeof(next),0);
  cnt:=0;
  read(n,m);
  for i:=1 to m do
   begin
    read(x,y,z);
    addedge(x,y,z);
    addedge(y,x,z);
   end;
 end;

procedure spfa;
 var
  l,r,i:longint;
 begin
  fillchar(vis,sizeof(vis),false);
  fillchar(d,sizeof(d),6);
  d[1]:=0;
  vis[1]:=true;
  l:=0;r:=1;
  q[r]:=1;
  while l<>r do
   begin
    inc(l);
    if l>100000 then l:=1;
    i:=head[q[l]];
    while i<>0 do
     begin
      if d[w[i]]>d[q[l]]+v[i] then
       begin
        d[w[i]]:=d[q[l]]+v[i];
        if not vis[w[i]] then
         begin
          vis[w[i]]:=true;
          inc(r);
          if r>100000 then r:=1;
          q[r]:=w[i];
         end;
       end;
      i:=next[i];
     end;
    vis[q[l]]:=false;
   end;
  if d[n]<100000000 then writeln(d[n]) else writeln(-1);
 end;

begin
 assign(input,'hardest.in');reset(input);
 assign(output,'hardest.out');rewrite(output);
 readln(t);
 for p:=1 to t do
  begin
   init;
   spfa;
  end;
 close(input);close(output);
end.