type ref=^elem;
     elem=record
            t,dest:integer;
            urm:ref;
          end;
const maxt=3500;
var n,m,p,k,a,b,c,i:integer;
    drum:array [1..150] of ref;
    amen:array [1..150,0..maxt] of integer;
    mita:array [1..150,0..maxt] of longint;

procedure prel;
var i,j:integer;
    q:ref;
begin
  fillchar(mita,sizeof(mita),255);
  mita[1,0]:=0;
  for j:=0 to maxt do
    for i:=1 to n do
      if mita[i,j]>-1
        then  begin
                mita[i,j]:=mita[i,j]+amen[i,j];
                q:=drum[i];
                while q<>nil do
                  begin
                    if (j+q^.t<=maxt)and(mita[i,j]>mita[q^.dest,j+q^.t])
                      then  mita[q^.dest,j+q^.t]:=mita[i,j];
                    q:=q^.urm;
                  end;
              end;

end;

procedure pune(a,b,c:integer);
var q:ref;
begin
  new(q);
  q^.t:=c;
  q^.dest:=b;
  q^.urm:=drum[a];
  drum[a]:=q;
end;

begin
  assign(output,'amenzi.out');
  rewrite(output);
  assign(input,'amenzi.in');
  reset(input);
  readln(n,m,k,p);
  for i:=1 to m do
    begin
      readln(a,b,c);
      pune(a,b,c);
      pune(b,a,c);
    end;
  for i:=1 to n do
    pune(i,i,1);
  for i:=1 to k do
    begin
      readln(a,b,c);
      amen[a,b]:=c;
    end;
  prel;
  for i:=1 to p do
    begin
      readln(a,b);
      writeln(mita[a,b]);
    end;
  close(input);
  close(output);
end.