program cojs_p1254;
var
	t,i,j,he,ta,tot,n,m:longint;
	head,next,v,w:array[0..10000] of longint;
	x,y,k:longint;
	q:array[0..100000] of longint;
	inq:array[0..200] of boolean;
	dist:array[0..200] of longint;
procedure ass;
begin
	assign(input,'hardest.in');
	assign(output,'hardest.out');
	reset(input);
	rewrite(output);
end;
procedure cls;
begin
	close(input);
	close(output);
end;
procedure add(x,y,z:longint);
begin
	inc(tot);
	v[tot]:=y; w[tot]:=z;
	next[tot]:=head[x];
	head[x]:=tot;
end;
procedure init;
var
	i,x,y,z:longint;
begin
	fillchar(head,sizeof(head),0);
	fillchar(next,sizeof(next),0);
	fillchar(v,sizeof(v),0);
	fillchar(w,sizeof(w),0);
	tot:=0;
    readln(n,m);
	for i:=1 to m do
	begin
		readln(x,y,z);
		add(x,y,z);
		add(y,x,z);
	end;
end;
{procedure spfa(st:longint);
var
	he,ta,x,y,k:longint;
	q:array[0..100000] of longint;
	inq:array[0..200] of boolean;
	dist:array[0..200] of longint;
begin
	fillchar(dist,sizeof(dist),$7f);
	dist[st]:=0;
	fillchar(inq,sizeof(inq),false);
	he:=0; ta:=1;
	q[1]:=st;
	inq[st]:=true;
	while he<ta do
	begin
		inc(he);
		x:=q[he];
		k:=head[x];
		y:=v[k];
		inq[x]:=false;
		while k<>0 do
		begin
			if dist[x]+w[k]<dist[y]
			then begin
				dist[y]:=dist[x]+w[k];
				if not(inq[y])
				then begin inc(ta); q[ta]:=y; inq[y]:=true; end;
			end;
			k:=next[k];
			y:=v[k];
		end;
	end;
	if dist[n]<>maxlongint
		then writeln(dist[n])
		else writeln('-1');
end;}
begin
	ass;
	readln(t);
	for i:=1 to t do
	begin
		init;
		for j:=1 to n do
                        dist[j]:=maxlongint;
		dist[1]:=0;
		fillchar(inq,sizeof(inq),false);
		he:=0; ta:=1;
		q[1]:=1;
		inq[1]:=true;
		while he<ta do
		begin
			inc(he);
			x:=q[he];
			k:=head[x];
			y:=v[k];
			inq[x]:=false;
			while k<>0 do
			begin
				if dist[x]+w[k]<dist[y]
				then begin
					dist[y]:=dist[x]+w[k];
					if not(inq[y])
					then begin inc(ta); q[ta]:=y; inq[y]:=true; end;
				end;
				k:=next[k];
				y:=v[k];
			end;
		end;
		if dist[n]<>maxlongint
			then writeln(dist[n])
			else writeln('-1');
	end;
	cls;
end.