program cogsp1254;
const max=50000;
var   q:array[1..max] of longint;
      b:array[1..20000,1..3] of longint;
      d,a:array[1..200] of longint;
      mark:array[1..200] of boolean;
      t,l,z,n,m,i,head,tail,u,v,w,s,k,now:longint;
begin
    readln(t);
    for l:=1 to t do begin
    fillchar(b,sizeof(b),0);
    fillchar(a,sizeof(a),0);
    z:=0;
        readln(n,m);
        for i:=1  to m do begin
            readln(u,v,w);
            inc(z);b[z,1]:=v;b[z,2]:=w;b[z,3]:=a[u];a[u]:=z;
            inc(z);b[z,1]:=u;b[z,2]:=w;b[z,3]:=a[v];a[v]:=z;
        end;
        head:=1;tail:=1;q[1]:=1;
        fillchar(mark,sizeof(mark),false);
        for i:=2 to n do d[i]:=maxlongint;
        mark[1]:=true;
        while head>=tail do begin
            k:=q[tail];s:=a[k];
            tail:=tail mod max+1;
            while s<>0 do begin
                now:=b[s,1];
                if d[now]>d[k]+b[s,2] then begin
                    d[now]:=d[k]+b[s,2];
                    if not mark[now] then begin
                        head:=head mod max+1;
                        q[head]:=now;
                    end;
                end;
                s:=b[s,3];
            end;
            mark[k]:=false;
        end;
        if d[n]=maxlongint then writeln(-1)
            else writeln(d[n]);
    end;
end.