const maxn=150;maxtimp=3501;maxtest=8000;
type pnod=^tnod;tnod=record nod,timp:longint;next:Pnod;end;
var t:TExt;
   G:array[0..maxn]of pnod;cur:Pnod;
   V,kapa:Array[0..maxtimp,0..maxn]of longint;
   Poras,Ptimp:Array[0..maxtest]of longint;
   costnou,orasnou,timpnou,timp,oras,n,m,k,p,i,a,b,c:longint;
begin
   assign(t,'amenzi.in');reset(t);readln(t,n,m,k,p);
   for i:=1 to M do
   begin
      readln(t,a,b,c);
      new(cur);cur^.timp:=c;cur^.nod:=a;cur^.next:=G[b];G[b]:=cur;
      new(cur);cur^.timp:=c;cur^.nod:=b;cur^.next:=G[a];G[a]:=cur;
   end;
   for i:=1 to K do begin readln(t,a,b,c);inc(kapa[b,a],c);end;
   for i:=1 to P do readln(t,Poras[i],Ptimp[i]);close(T);
   for timp:=0 to maxtimp do for oras:=1 to N do V[timp,oras]:=-1;V[0,1]:=0;
   for timp:=0 to maxtimp-1 do for oras:=1 to N do if V[timp,oras]>=0 then
   begin
      if V[timp+1,oras]<V[timp,oras] then V[timp+1,oras]:=V[timp,oras];
      cur:=G[oras];
      while cur<>nil do
      begin
         orasnou:=cur^.nod;timpnou:=timp+cur^.timp;
         if (timpnou<=maxtimp) then
         begin
            costnou:=Kapa[timpnou,orasnou]+V[timp,oras];
            if costnou>V[timpnou,orasnou] then V[timpnou,orasnou]:=costnou;
         end;
         cur:=cur^.next;
      end;
   end;
   assign(t,'amenzi.out');rewrite(T);
   for i:=1 to P do writeln(t,V[Ptimp[i],Poras[i]]);close(T);
end.