#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 128
#define MAX_T 4096
#define INF 0x3f3f3f3f
#define FIN "amenzi.in"
#define FOUT "amenzi.out"
#define mp make_pair
#define pb push_back
#define f first
#define s second

int N, M, K, P, tax[MAX_T][MAX_N], bst[MAX_T][MAX_N];
vector < pair<int, int> > G[MAX_N];

int main(void)
{
    int i, j, a, b, c;
    vector< pair<int, int> >::iterator it; 

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    for (scanf("%d %d %d %d", &N, &M, &K, &P); M; M--)
    {
        scanf("%d %d %d", &a, &b, &c);
        a--, b--;
        G[a].pb(mp(b, c));
        G[b].pb(mp(a, c));
    }
    for (i = 0; i < N; i++)
        sort(G[i].begin(), G[i].end());

    for (; K; K--)
    {
        scanf("%d %d %d", &a, &b, &c);
        tax[b][a-1] = c;
    }

    for (i = 0; i < MAX_T; i++)
        for (j = 0; j < N; j++)
            bst[i][j] = -INF;
    bst[0][0] = 0;

    for (i = 0; i+1 < MAX_T; i++)
        for (j = 0; j < N; j++)
        {
            bst[i+1][j] = max(bst[i+1][j], bst[i][j]+tax[i+1][j]);
            for (it = G[j].begin(); it != G[j].end(); it++)
            {
                if (i+it->s >= MAX_T) break;
                bst[i+it->s][it->f] = max(bst[i+it->s][it->f], bst[i][j]+tax[i+it->s][it->f]);
            }
        }

    for (; P; P--)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", bst[b][a-1]);
    }

    return 0;
}