#include <stdio.h>
#define MAXN 150
#define MAXM 1500
#define MAXT 3500
int vf[2 * MAXM + 1], next[2 * MAXM + 1], cost[2 * MAXM + 1], ult[MAXN + 1];
int infr[MAXT + 1][MAXN + 1];
int tab[MAXT + 1][MAXN + 1];
int max[MAXN + 1];
inline int max2(int a, int b){
return a > b ? a : b;
}
inline void calctab(int n){
int i, j, poz;
tab[0][1] = 1 + infr[0][1]; //pe 1 il scad la final
max[1] = tab[0][1];
for(i = 0; i <= MAXT; i++){
for(j = 1; j <= n; j++){
poz = ult[j];
while(poz > 0){
if(i >= cost[poz]){
if(tab[i - cost[poz]][vf[poz]] != 0){
tab[i][j] = max2(tab[i - cost[poz]][vf[poz]] + infr[i][j], max[j]);
}
if(tab[i][j] > max[j]) max[j] = tab[i][j];
}
poz = next[poz];
}
}
}
}
inline void add(int x, int y, int c, int *dr){
vf[*dr] = y;
cost[*dr] = c;
next[*dr] = ult[x];
ult[x] = *dr;
(*dr)++;
}
int main(){
FILE *in = fopen("amenzi.in", "r");
int n, m, k, p, i, x, y, c, dr;
fscanf(in, "%d%d%d%d", &n, &m, &k, &p);
dr = 1;
for(i = 1; i <= m; i++){
fscanf(in, "%d%d%d", &x, &y, &c);
add(x, y, c, &dr);
add(y, x, c, &dr);
}
for(i = 1; i <= k; i++){
fscanf(in, "%d%d%d", &x, &y, &c);
infr[y][x] = c;
}
calctab(n);
FILE *out = fopen("amenzi.out", "w");
for(i = 0; i < p; i++){
fscanf(in, "%d%d", &x, &y);
fprintf(out, "%d\n", tab[y][x] - 1);
}
fclose(in);
fclose(out);
return 0;
}