type    nodd=record
                y,d,n:longint;
        end;

var     a,q,d:array[0..210]of longint;
        b:array[0..21000]of nodd;
        bb:array[0..210]of boolean;
        n,m,i,j,x,y,h,t,tt,p,k:longint;

procedure add(x,y:longint);
begin
        inc(t); b[t].y:=y; b[t].d:=p;
        b[t].n:=a[x]; a[x]:=t;
end;

procedure init;
begin
        readln(n,m); t:=0;
        fillchar(a,sizeof(a),0);
        for i:=1 to m do
        begin
                read(x,y,p);
                add(x,y);
                add(y,x);
        end;
end;

procedure work;
begin
        fillchar(bb,sizeof(bb),true); bb[1]:=false;
        fillchar(d,sizeof(d),$0f); d[1]:=0;
        h:=0; t:=1; q[1]:=1;
        while h<>t do
        begin
                inc(h);if h>200 then h:=1;
                x:=q[h]; p:=a[x];
                while p<>0 do
                begin
                        y:=b[p].y;
                        if d[y]>d[x]+b[p].d then
                        begin
                                d[y]:=d[x]+b[p].d;
                                if bb[y] then
                                begin
                                        inc(t); if t>200 then t:=1;
                                        q[t]:=y; bb[y]:=false;
                                end;
                        end;
                        p:=b[p].n;
                end;
                bb[x]:=true;
        end;
        if d[n]=d[0] then writeln(-1) else writeln(d[n]);
end;

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