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;
mita,amen: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);
inc(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.