#include <stdio.h>

#define Nmax 151
#define Tmax 3501

int best[Nmax][Tmax];
int tax[Nmax][Tmax];
int cost[Nmax][Nmax];
int l[Nmax][Nmax];
int n,m,k,p;

int main()
{
     freopen("amenzi.in","r",stdin);
     freopen("amenzi.out","w",stdout);
     
     scanf("%d%d%d%d", &n,&m,&k,&p);
     
     int a,b,c;
     
     for (int i=1;i<=m;++i)
     {
          scanf("%d%d%d", &a,&b,&c);
          l[a][++l[a][0]] = b;
          cost[a][l[a][0]] = c;
          l[b][++l[b][0]] = a;
          cost[b][l[b][0]] = c;
     }
     
     for (int i=1;i<=k;++i)
     {
          scanf("%d%d%d", &a,&b,&c);
          tax[a][b] = c;
     }     
     
     for (int i=2;i<=n;++i)
          best[i][0] = -123456789;
     
     for (int j=1;j<=3500;++j)
     for (int i=1;i<=n;++i)
     {
          best[i][j] = best[i][j-1] + tax[i][j];
          for (k=1;k<=l[i][0];++k)
               if (j >= cost[i][k])
                    if (best[i][j] < tax[i][j] + best[l[i][k]][j-cost[i][k]])
                         best[i][j] = tax[i][j] + best[l[i][k]][j-cost[i][k]];
     }
     
     for (int i=1;i<=p;++i)
     {
          scanf("%d%d", &a,&b);
          printf("%d\n", best[a][b]);     
     }
     
     
     return 0;     
}