var
  t,i,j,n,m,k,p,x,y,tmax:longint;
  inf:array[0..160,0..3600] of longint;
  a:array[0..3030,1..3] of longint;
  st:array[0..160] of longint;
  date:array[0..8080,1..2] of longint;
  {sol:array[0..8080] of longint;}
  din:array[0..160,0..3600] of longint;

procedure Sort(l, r: longint);
var
  i, j, x, y: longint;
begin
  i := l; j := r; x := a[(l+r) DIV 2,1];
  repeat
    while a[i,1] < x do i := i + 1;
    while x < a[j,1] do j := j - 1;
    if i <= j then
    begin
      y := a[i,1]; a[i,1] := a[j,1]; a[j,1] := y;
      y := a[i,2]; a[i,2] := a[j,2]; a[j,2] := y;
      y := a[i,3]; a[i,3] := a[j,3]; a[j,3] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;

begin
  assign(input,'amenzi.in');
  reset(input);
  readln(n,m,k,p);
  j:=0;
  for i:=1 to m do
  begin
    inc(j);
    readln(a[j,1],a[j,2],a[j,3]);
    inc(j);
    a[j,1]:=a[j-1,2];
    a[j,2]:=a[j-1,1];
    a[j,3]:=a[j-1,3];
  end;
  for i:=1 to n do
  begin
    inc(j);
    a[j,1]:=i;
    a[j,2]:=i;
    a[j,3]:=1;
  end;
  m:=j;
  sort(1,m);
  st[n+1]:=m+1;
  for i:=m-1 downto 0 do
    if a[i,1]<>a[i+1,1] then st[a[i+1,1]]:=i+1;
  for i:=n downto 1 do
    if st[i]=0 then st[i]:=st[i+1];
  for i:=1 to k do
  begin
    read(x,y,j);
    inc(inf[x,y],j);
  end;
  tmax:=0;
  for i:=1 to p do
  begin
    read(date[i,1],date[i,2]);
    if date[i,2]>tmax then tmax:=date[i,2];
  end;
  close(input);
  fillchar(din,sizeof(din),255);

  din[1,0]:=inf[1,0];
  tmax:=tmax+5;
  for t:=0 to tmax do
    for x:=1 to n do
      if din[x,t]<>-1 then
      begin
        {if date[x,t]<>0 then sol[date[x,t]]:=din[x,t];}
        for i:=st[x] to st[x+1]-1 do
          if din[x,t]+inf[a[i,2],t+a[i,3]]>din[a[i,2],t+a[i,3]] then din[a[i,2],t+a[i,3]]:=din[x,t]+inf[a[i,2],t+a[i,3]];
      end;

  assign(output,'amenzi.out');
  rewrite(output);
  for i:=1 to p do
  begin
    writeln(din[date[i,1],date[i,2]]);
  end;
  close(output);
end.