var f,f2:text;
    n,m,p,k,i,x,y,l,j:integer;
    a:array[0..150,1..150] of integer;
    b:array[0..3501,1..150] of longint;
    c:array[1..150,0..3501] of integer;
begin
for i:=1 to 150 do
    for j:=0 to 3500 do b[j,i]:=-1;
b[0,1]:=0;
assign(f2,'amenzi.out');
rewrite(f2);
assign(f,'amenzi.in');
reset(f);
readln(f,n,m,k,p);
for i:=1 to m do begin
                 read(f,x,y);
                 readln(f,a[x,y]);
                 a[y,x]:=a[x,y];
                 end;
for i:=1 to k do begin
                 read(f,x,y);
                 readln(f,c[x,y]);
                 end;
for i:=0 to 3500 do
    for j:=1 to n do
        if b[i,j]<>-1 then begin
                           if b[i,j]+c[j,i+1]>b[i+1,j] then b[i+1,j]:=b[i,j]+c[j,i+1];
                           for l:=1 to n do if a[j,l]<>0 then
                               if b[i,j]+c[l,i+a[j,l]]>b[i+a[j,l],l] then b[i+a[j,l],l]:=b[i,j]+c[l,i+a[j,l]];
                           end;
for i:=1 to p do begin
   readln(f,x,y);
   writeln(f2,b[y,x]);
   end;
close(f);
close(f2);
end.