#include <stdio.h>

#define infile "amenzi.in"
#define outfile "amenzi.out"
#define NMAX 155
#define TMAX 3505
#define INF 10000000
struct NOD {int x,c; NOD *adr;};

FILE *fin,*fout;
int n,m,k,p;
NOD *prim[NMAX];
int amenzi[TMAX][NMAX]; // amenda totala care se castiga daca la momentul t sunt in intersectia x
int profit[TMAX][NMAX]; // profitul obtinut pana in starea (t,x)
int drum_min[NMAX][NMAX];

inline void adaug_st(NOD *(&prim), int x, int c)
  {
   NOD *a=new NOD;
   a->x=x;
   a->c=c;
   a->adr=prim;
   prim=a;
  }

inline int max(int x, int y)
  {
   return (x>y)?x:y;
  }

inline int min(int x, int y)
  {
   return (x<y)?x:y;
  }


int main()
{
int i,j,u,v,c;
int inters,timp;
fin=fopen(infile,"r");
fout=fopen(outfile,"w");
fscanf(fin,"%d %d %d %d",&n,&m,&k,&p);
for(i=0;i<n;i++)
   prim[i]=NULL;
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      if(i==j)
        drum_min[i][j]=0;
      else
        drum_min[i][j]=INF;
for(i=0;i<m;i++)
   {
    fscanf(fin,"%d %d %d",&u,&v,&c);
    drum_min[u-1][v-1]=drum_min[v-1][u-1]=c;
    //drum_min[u-1][v-1]=min(drum_min[u-1][v-1],c);
    //drum_min[v-1][u-1]=drum_min[u-1][v-1];
   }
for(i=0;i<n;i++)
   for(j=0;j<n;j++)
      if(i!=j && drum_min[i][j]!=INF)
        adaug_st(prim[i],j,drum_min[i][j]);

for(i=0;i<3502;i++)
   for(j=0;j<n;j++)
      amenzi[i][j]=0;
for(i=0;i<k;i++)
   {
    fscanf(fin,"%d %d %d",&inters,&timp,&c);
    amenzi[timp][inters-1]+=c;
   }

NOD *b;
profit[0][0]=amenzi[0][0];
for(i=0;i<3502;i++)
   for(j=0;j<n;j++)
      if(i || j)
        {
         profit[i][j]=-1;
         b=prim[j];
         while(b)
              {
               if(i-b->c>=0)
                 profit[i][j]=max(profit[i][j],profit[i-b->c][b->x]);
               b=b->adr;
              }
         if(profit[i][j]!=-1)
           profit[i][j]+=amenzi[i][j];
         if(i && profit[i][j]<profit[i-1][j])
           profit[i][j]=profit[i-1][j];
        }

for(i=0;i<p;i++)
   {
    fscanf(fin,"%d %d",&u,&timp);
    fprintf(fout,"%d\n",profit[timp][u-1]);
   }

fclose(fin);
fclose(fout);
return 0;
}