/*
by vlad dumitriu
*/
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K, P, i, j;
int v[155][155];
int G[155][155];
int sol[3505][152];
int DA[8002][2];
struct nood{
	int nod, timp, cost;
	nood(const int &_nod, const int &_timp, const int &_cost) {nod = _nod; timp = _timp; cost = _cost;}
	nood(){};
	};
bool operator<(const nood &a, const nood &b) {
	if (a.timp<b.timp) return true;
	if (a.timp == b.timp) if (a.nod<b.nod) return true;
	if (a.timp == b.timp) if (a.nod == b.nod) if (a.cost < b.cost) return true;
	return false;
	}
int main() {
	freopen("amenzi.in", "r", stdin);
	freopen("amenzi.out", "w", stdout);
	scanf("%d %d %d %d", &N, &M, &K, &P);
	for (i=0; i<3501; i++) for (j=1; j<=N; j++) sol[i][j] = -1;
	for (i=0; i<M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (v[a][b] == 0) G[a][++G[a][0]] = b;
		if (v[b][a] == 0) G[b][++G[b][0]] = a;
		if (v[a][b] == 0 || c < v[a][b]) v[a][b] = c;
		if (v[b][a] == 0 || c < v[b][a]) v[b][a] = c;
		}
	//corect
	sol[0][1] = 0;
	vector<nood> V;
	for (i=0; i<K; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		//if (a == 1 && b == 0) sol[0][1]+=c;
		//else
		
			V.push_back(nood(a, b, c));		
			
		}
	sort(V.begin(), V.end());
	//corect
	/*for (i=0; i<V.size(); i++) {
		printf("%d %d %d\n", V[i].timp, V[i].nod, V[i].cost);
		}*/
	int POZ = 0, k;
	int PP = V.size();
	//faza aia
	int NMAX = 0;
	for (i=0; i<P; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		DA[i][0] = a; DA[i][1] = b;
		if (b > NMAX) NMAX = b;
		//printf("%d\n", sol[b][a]);
		}
	//checked
	for (i=0; i<=NMAX; i++) for (j=1; j<=N; j++) if (sol[i][j]!=-1) {
		//vad ci amenzi am in asta
		for (;POZ<PP&&V[POZ].timp < i; POZ++);
		for (;POZ<PP&&V[POZ].timp ==i && V[POZ].nod < j; POZ++);
		for (k=POZ; k<PP&&V[k].timp==i&&V[k].nod==j; k++) sol[i][j]+=V[k].cost;
		if (sol[i+1][j] < sol[i][j]) sol[i+1][j] = sol[i][j];//stau pe loci
		//if (i==0 && j == 1) printf("dau: %d %d\n", v[j][3], sol[3][3]);
		for (k=1; k<=G[j][0]; k++) if (v[j][G[j][k]] + i <= NMAX) 
			if (sol[v[j][G[j][k]]+i][G[j][k]] < sol[i][j])
			sol[v[j][G[j][k]]+i][G[j][k]]= sol[i][j]; 
		}
	for (i=0; i<P; i++) {
		//int a, b;
		//scanf("%d %d", &a, &b);
		printf("%d\n", sol[DA[i][1]][DA[i][0]]);
		}
	return 0;
}