program hardest;
const
  lim=10000;
var
  t,n,m,i,a,b,c,h,cnt,tot:longint;
  d,head:array[1..200]of longint;
  v:array[1..200]of boolean;
  next,e,w:array[1..20000]of longint;
  q:array[0..lim]of longint;
 
procedure insert(u,v,len:longint);
begin
  inc(tot);
  next[tot]:=head[u];
  head[u]:=tot;
  e[tot]:=v;
  w[tot]:=len;
end;
 
begin
  assign(input,'hardest.in');
  assign(output,'hardest.out');
  reset(input);
  rewrite(output);
  
  readln(cnt);
  while cnt>0 do
  begin
    readln(n,m);
    fillchar(head,sizeof(head),0);
    tot:=0;
    for i:=1 to m do
    begin
      readln(a,b,c);
      insert(a,b,c);
      insert(b,a,c);
    end;
    for i:=1 to n do d[i]:=maxlongint shr 1;
    fillchar(v,sizeof(v),0);
    d[1]:=0;
    h:=0;
    t:=1;
    q[1]:=1;
    v[1]:=true;
    while h<t do
    begin
      h:=(h+1)mod lim;
      i:=head[q[h]];
      while i<>0 do
      begin
        if d[e[i]]>d[q[h]]+w[i] then
        begin
          d[e[i]]:=d[q[h]]+w[i];
          if not v[e[i]]then
          begin
            t:=(t+1)mod lim;
            q[t]:=e[i];
            v[e[i]]:=true;
          end;
        end;
        i:=next[i];
      end;
      v[q[h]]:=false;
    end;
    if d[n]<maxlongint shr 1 then writeln(d[n])else writeln(-1);
    dec(cnt);
  end;
  
  close(input);
  close(output);
end.