var
q:array [1..5000]of longint;
dist:array [0..300]of longint;
vis:array [0..300]of boolean;
pre:array [0..300]of longint;
cost:array [0..300,0..300]of longint;
i,n,m,v,a,b,e,t,j:longint;
procedure spfa(v0:longint);
 var i,h,t,k:longint;
 begin
  fillchar(vis,sizeof(vis),false);
  for i:=1 to n do dist[i]:=maxlongint;
  h:=0;
  t:=1;
  q[1]:=v0;
  dist[v0]:=0;
  vis[v0]:=true;
  repeat
   h:=h mod 5000+1;
   k:=q[h];
   for i:=1 to n do
    if  (dist[k]+cost[k,i]<dist[i]) and(cost[k,i]<>-1) then
	begin
	 dist[i]:=dist[k]+cost[k,i];
        // pre[i]:=k;
	if not vis [i] then
	begin
	 t:=t mod 5000+1;
	 q[t]:=i;
	 vis[i]:=true;
	end;
        end;
      vis[k]:=false;
     until h=t;
  end;
  procedure init;
  var i,j:longint;
   begin
   readln(n,m);
   for i:=1 to n do
   for j:=1 to n do
   cost [i,j]:=-1;
   for i:=1 to m do
   begin
   readln(a,b,e);
   cost[a,b]:=e;
   cost[b,a]:=e;
   end;
   end;
  begin
  assign(input,'hardest.in'); assign(output,'hardest.out');
  reset(input);rewrite(output);
  readln(t);
  for j:=1 to t do
   begin
    init;
    spfa(1);
    if dist[n]<>maxlongint then
    writeln(dist[n]) else writeln(-1);
   end;
   close(input);
   close(output);
  end.