type point=^node;
	node=record
	data,w:longint;
	next:point;
	end;

var n,m,st,ed,i,j,x,y,z,fa,t,k:longint;
		son:array[1..210] of point;
		p:point;
		d,ans:array[1..210] of longint;
		pd:array[1..210] of boolean;
		b:array[1..1000000] of longint;


procedure print;
begin
writeln('No way');
close(input);
close(output);
halt;
end;


begin
assign(input,'hardest.in');
assign(output,'hardest.out');
reset(input);
rewrite(output);

readln(t);

for k:=1 to t do
	begin


	readln(n,m);

        for i:=1 to n do
                begin
                d[i]:=20000000;
                son[i]:=nil;
                end;


	for i:=1 to m do
		begin
		readln(x,y,z);
		new(p);
		p^.data:=y;
		p^.w:=z;
		p^.next:=son[x];
		son[x]:=p;
		new(p);
		p^.data:=x;
		p^.w:=z;
		p^.next:=son[y];
		son[y]:=p;
		end;



d[1]:=0;
i:=1;
j:=2;
b[1]:=1;
pd[1]:=true;
while i<>j do
	begin
	fa:=b[i];
	p:=son[fa];
	while p<>nil do
		begin
		if d[fa]+p^.w<d[p^.data] then
			begin
			d[p^.data]:=d[fa]+p^.w;
			//dp[p^.data]:=fa;
			//inc(p^.num);
			//if p^.num>m+1 then print;
			if not pd[p^.data] then
				begin
				b[j]:=p^.data;
				pd[p^.data]:=true;
				j:=(j mod 1000000)+1;
				end;
			end;
		p:=p^.next;
		end;
	pd[fa]:=false;
	i:=(i mod 1000000)+1;
	end;

	if d[n]<10000000 then writeln(d[n]) else writeln(-1);

end;
	
close(input);
close(output);
end.