#include <stdlib.h>
#include <stdio.h>

int a[150][150];

int t[150][3500];


int n,m,k,p;

int my[12000], mx[12000], mcost[12000];

  void calcmin(){
        int x,y,z;
        for(z=0;z<n;z++)
          for(x=0;x<n;x++)
            for(y=0;y<n;y++)
              if(x!=y&&a[x][z]!=0&&a[z][y]!=0)
               if(a[x][z]+a[z][y]<a[x][y]||a[x][y]==0)
                 a[x][y]=a[x][z]+a[z][y];
  }
  void inversaret(int &i, int &j){
    int aux=i;
    i=j;
    j=aux;
  }
  void inversare(int i, int j){
     inversaret(mx[i],mx[j]);
     inversaret(my[i],my[j]);
     inversaret(mcost[i],mcost[j]);
  }
  int sortmij(int s, int f){
    int d=1;
    while(s<f){
      if(my[s]>mx[f])
        { inversare(s, f);
          d=1-d;
        }
          s+=d;
          f-=1-d;
    }
    return s;
  }

  void sortare(int s, int f){
        if(s>=f)return;
    int m=sortmij(s, f);
    sortare(s, m-1);
    sortare(m+1, f);
  }
  
int main(){
         FILE *fin=fopen("amenzi.in", "r");
         FILE *fout=fopen("amenzi.out", "w");
        fscanf(fin,"%d%d%d%d", &n, &m, &k, &p);
        int i, x, y, cost;

        for(i=0;i<m;i++)
         {
           fscanf(fin,"%d%d%d", &x, &y, &cost);
           a[x-1][y-1]=a[y-1][x-1]=cost;

         }
         calcmin();
         int aj, o, j, z=0;
         for(i=0;i<k;i++)
         {
           fscanf(fin,"%d%d%d", &x, &y, &cost);
           x--;
           if(y>3500) continue;
           if(a[0][x]==0||a[0][x]>y) continue;
           mx[z]=x; my[z]=y; mcost[z]=cost;
           z++;
         } k=z;
           sortare(0, k-1);
         for(i=0;i<k;i++)
         {
           x=mx[i];
           y=my[i];
           cost=mcost[i];
           //if(t[x][y]==0)
             for(o=y-1;o>=a[0][x];o--) if(t[x][o]>t[x][y]) {t[x][y]=t[x][o];}
           t[x][y]+=cost;
//           printf("in %d  la %d cost %d (%d)\n",x+1, y, t[x][y], cost);
           for(j=0;j<n;j++){
              if(j!=x){

               aj=y+a[x][j];
               //if(t[j][aj]==0)
                 for(o=aj-1;o>=a[0][j];o--) if(t[j][o]>t[j][aj]) {t[j][aj]=t[j][o];}
               if(t[j][aj]<t[x][y]){
                 t[j][aj]=t[x][y];
  //               printf("imb in %d la %d  total %d\n",j+1, aj, t[j][aj]);
                 }
              }
            }
         }


         for(i=0;i<p;i++)
         {
           fscanf(fin,"%d%d", &x, &y);
           x--;
           if(t[x][y]==0)
             for(o=y;o>=a[0][x];o--) if(t[x][o]!=0) {t[x][y]=t[x][o]; break;}
    //       printf("in %d la %d = %d\n",x+1, y, t[x][y]);
        fprintf(fout, "%d\n", t[x][y]);
         }
                                     fclose(fout);
                                     fclose(fin);
        return 0;
}