#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define Tmax 3650
#define Nmax 160
#define pb push_back
#define mk make_pair

int best[Tmax][Nmax];
int ev[Tmax][Nmax];

vector<int> l[Nmax], c[Nmax];


void fuck(int i,int j)
{
	if(best[i+1][j] < best[i][j] + ev[i+1][j])
		best[i+1][j] = best[i][j] + ev[i+1][j];

	for (int k=0;k<l[j].size();++k)
		if(i+c[j][k] < Tmax && best[i+c[j][k]][l[j][k]] < best[i][j] + ev[i+c[j][k]][l[j][k]])
			best[i+c[j][k]][l[j][k]] = best[i][j] + ev[i+c[j][k]][l[j][k]];
}	


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

	int n,m,k,p,a,b,C;

	scanf("%d%d%d%d",&n,&m,&k,&p);

	for (int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&C);
		--a, --b;
		l[a].pb(b);	c[a].pb(C);
		l[b].pb(a);	c[b].pb(C);
	}

	for (int i=1;i<=k;++i)
	{
		scanf("%d%d%d",&a,&b,&C);
		ev[b][a-1] = C;
	}
	
/*	
	for (int i=0;i<Tmax;++i)
		memset(best[i],-1,sizeof(best[i]));
*/
	best[0][0] = ev[0][0];

	for (int i=0;i<=3521;++i)
		for (int j=0;j<n;++j)
			if(best[i][j] >= 0)
				fuck(i,j);

	for (int i=1;i<=p;++i)
	{
		scanf("%d%d",&b,&a);
		printf("%d\n",best[a][b-1]);
	}

	return 0;
}