#include <stdio.h>
#include <memory.h>

#define MMAX 1502
#define NMAX 152
#define TMAX 3501
#define INFI 0x3f3f3f3f

int best[TMAX][NMAX], time[TMAX][NMAX];
int n, m, k, p;
int a[MMAX], b[MMAX], c[MMAX];

void read()
{
	int i, t, x, y;
	scanf("%d%d%d%d", &n, &m, &k, &p);
	for(i = 1; i <= m; ++i)
		scanf("%d%d%d", &a[i], &b[i], &c[i]);
	for(i = 1; i <= k; ++i)
	{
		scanf("%d%d%d", &x, &t, &y);
		time[t][x] += y;
	}
}

inline int MAX(int a, int b) {	return (a > b) ? (a) : (b); }

void dinamic()
{
     //printf("%d %d\n", n, m);
	int i, j;
	memset(best, -INFI, sizeof(best));
	//for(j = 1; j <= n; ++j)
	best[0][1] = time[0][1];

	for(i = 1; i < TMAX; ++i)
	{
		for(j = 1; j <= m; ++j)
		{
			best[i][ a[j] ] = MAX(best[i][ a[j] ], best[i-1][ a[j] ]);
			if(i - c[j] >= 0)
				best[i][ a[j] ] = MAX(best[i][ a[j] ], best[ i - c[j] ][ b[j] ]);

			best[i][ b[j] ] = MAX(best[i][ b[j] ], best[i-1][ b[j] ]);
			if(i - c[j] >= 0)
				best[i][ b[j] ] = MAX(best[i][ b[j] ], best[ i - c[j] ][ a[j] ]);

             //printf("%d %d\n", best[i][ a[j] ], best[i][ b[j] ]);
		}
		for(j = 1; j <= n; ++j)
			best[i][j] += time[i][j];
	}
}

void print(int best[TMAX][NMAX])
{
    for(int i = 0; i < 59; ++i)
    {
     for(int j = 1; j <= n; ++j)
           printf("%d ", best[i][j]);
     printf("\n");
    }
    printf("\n");
}

int main()
{
	freopen("amenzi.in", "r", stdin);
	freopen("amenzi.out", "w", stdout);

	read();

    dinamic();

	for(int i = 0, x, y; i < p; ++i)
	{
		scanf("%d%d", &x, &y);
		printf("%d\n", best[y][x]);
	}
    ///print(best);
    //print(time);

	return 0;
}