type adr=^rec;
     rec=record
          urm:adr;
          x,c:integer;
         end;
var fi,fo:text;
    x,y,cc,i,j,n,m,k,nrp:integer;
    la:array[0..3501]of adr;
    a,b,c:array[1..1500]of integer;
    max:array[0..3501,1..150]of longint;
    p:adr;
begin
 assign(fi,'amenzi.in'); reset(fi);
 assign(fo,'amenzi.out'); rewrite(fo);
 readln(fi,n,m,k,nrp);
 for i:=1 to m do readln(fi,a[i],b[i],c[i]);
 for i:=1 to k do
  begin
        readln(fi,x,y,cc);
        new(p); p^.urm:=la[y]; p^.x:=x; p^.c:=cc;la[y]:=p;
  end;
 max[0,1]:=1;
 for i:=0 to 3500 do
  begin
        p:=la[i];
        while p<>nil do
         begin
               if max[i,p^.x]<>0 then inc(max[i,p^.x],p^.c);
               p:=p^.urm;
         end;
        for j:=1 to m do
         if i+c[j]<=3500 then
          begin
                if max[i,a[j]]<>0 then
                 if max[i,a[j]]>max[i+c[j],b[j]] then
                  max[i+c[j],b[j]]:=max[i,a[j]];
                if max[i,b[j]]<>0 then
                 if max[i,b[j]]>max[i+c[j],a[j]] then
                  max[i+c[j],a[j]]:=max[i,b[j]];
          end;
        for j:=1 to n do
         if max[i,j]>max[i+1,j]then
          max[i+1,j]:=max[i,j];
  end;
 for i:=1 to nrp do
  begin
        readln(fi,x,y);
        writeln(fo,max[y,x]-1);
  end;
 close(fo);
end.