var
  n,i,j,k,l,m,q,best:longint;
  f:array[1..100,1..100] of longint;
  u,v,e:array[1..10000] of longint;
  minnum:array[1..100] of longint;
  visit:array[1..100] of boolean;
function min(x,y:longint):longint;
  begin if x<y then exit(x) else exit(y); end;
procedure search(v,rest,pass:longint);
  begin
    if minnum[v]+pass>=best then exit;
    if rest=0 then begin
      if pass<best then best:=pass;
      exit;
    end;
    for i:=1 to n do
      if not visit[i] then begin
        visit[i]:=true;
        search(i,rest-1,pass+f[v,i]);
        visit[i]:=false;
      end;
  end;
procedure work;
  begin
    filldword(f,sizeof(f)>>2,maxlongint>>2);
    filldword(minnum,sizeof(minnum)>>2,maxlongint>>2);
    for i:=1 to n do f[i,i]:=1;
    for i:=1 to m do f[u[i],v[i]]:=e[i];
    for k:=1 to n do
      for i:=1 to n do
        for j:=1 to n do
          f[i,j]:=min(f[i,j],f[i,k]+f[k,j]);
    best:=maxlongint;
    for i:=1 to n do
      for j:=1 to n do
        if i<>j then
          minnum[i]:=min(minnum[i],f[i,j]);
    search(1,n-1,0);
    writeln(best);
  end;
begin
assign(input,'tubea.in');reset(input);
assign(output,'tubea.out');rewrite(output);
  readln(n,m); visit[1]:=true;
  for k:=1 to m do readln(u[k],v[k],e[k]);
  work;
  readln(q);
  for l:=1 to q do begin
    readln(k,e[k]);
    work;
  end;
close(input); close(output);
end.