const maxtimp=3500;maxn=150;maxtest=8000;
type pnod=^Tnod;tnod=record nod,timp:longint;next:Pnod;end;
var t:Text;
   V,Kapa:Array[0..maxtimp,0..maxn]of longint;
   Pa,Pb:array[0..maxtest]of longint;
   G:array[0..maxn]of pnod;cur:Pnod;
   noucost,noutimp,nouoras,timp,oras,i,n,j,m,k,p,a,b,c:longint;
begin
   for i:=0 to maxtimp do for j:=0 to maxn do V[i,j]:=-1;v[0,1]:=0;
   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^.nod:=a;cur^.timp:=c;cur^.next:=G[b];G[b]:=cur;
      new(cur);cur^.nod:=b;cur^.timp:=c;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,Pa[i],Pb[i]);close(t);
   for timp:=0 to maxtimp do for oras:=1 to N do if V[timp,oras]>=0then
   begin
      cur:=G[oras];
      while cur<>nil do
      begin
         noutimp:=cur^.timp+timp;nouoras:=cur^.nod;
         noucost:=V[timp,oras]+Kapa[noutimp,nouoras];
         if V[noutimp,nouoras]<noucost then V[noutimp,nouoras]:=noucost;
         cur:=cur^.next;
      end;
   end;
   assign(t,'amenzi.out');rewrite(T);
   for i:=1 to P do writeln(t,V[Pb[i],Pa[i]]);close(T);
end.