var
a,b,c,d,m,n,x,y,z,o:longint;

k:array[0..200,0..200]of longint;
l,h:array[0..50000]of longint;
procedure bfs(q,e:longint);
var
p,g,t,i,j:longint;
begin
t:=maxlongint;
for i:=q to e do
if (l[i]=n)and(t>h[i]) then
t:=h[i];
if t<>maxlongint then
begin
o:=t;
exit;
end;

j:=e;

for g:=q to e do
for p:=1 to n do
if p<>l[g] then
if k[l[g],p]<>0 then
begin
j:=j+1;
l[j]:=p;
h[j]:=h[g]+k[l[g],p];
end;
if (e+1<=j)and(j<50000) then
bfs(e+1,j);

end;
begin
assign(input,'hardest.in');
assign(output,'hardest.out');
reset(input);
rewrite(output);
readln(a);
for b:=1 to a do
begin
read(n,m);

for c:=1 to m do
begin
readln(x,y,z);
if (k[x,y]>z)or(k[x,y]=0) then
begin
k[x,y]:=z;
k[y,x]:=z;
end;
end;
l[1]:=1;
h[1]:=0;

bfs(1,1);
if o<>0 then
writeln(o)
else
writeln(-1);
end;
close(input);
close(output);
end.