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

using namespace std;

#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define sz size()
#define nmax 128
#define tmax 4096
#define inf 1000111000

int n,m,k,p;
vector < pair <int,int> > G[nmax];
int A[tmax][nmax],S[tmax][nmax];
int TT=0;

int main()
{
	FILE *fi=fopen("amenzi.in","r"),*fo=fopen("amenzi.out","w");
	fscanf(fi,"%d %d %d %d",&n,&m,&k,&p);
	int i,j,a,b,c;
	FOR(i,0,m)
	{
		fscanf(fi,"%d %d %d",&a,&b,&c);
		if(a>100||b>100)
			printf("AAA\n");
		a--,b--;
		G[a].pb(mp(b,c));
		G[b].pb(mp(a,c));
	}

	FOR(i,0,k)
	{
		fscanf(fi,"%d %d %d",&a,&b,&c);
		if(a>100)
			printf("BBB\n");
		a--;
		S[b][a]+=c;
		TT>?=b;
	}
	
	FOR(i,0,tmax) FOR(j,0,n)
	{
		A[i][j]=0+(!i&&!j);
		if(i)
			A[i][j]=A[i-1][j];
		FOR(a,0,G[j].sz)
			if(i>=G[j][a].s&&A[i-G[j][a].s][G[j][a].f])
			{

				A[i][j]>?=A[i-G[j][a].s][G[j][a].f];
			}
		if(A[i][j])
			A[i][j]+=S[i][j];
	}

	FOR(i,0,p)
	{
		fscanf(fi,"%d %d",&a,&b);
		if(a>100)
			printf("CCC\n");
		TT>?=b;
		a--;
		fprintf(fo,"%d\n",A[b][a]-1);
	}
	fclose(fi);
	fclose(fo);
	fprintf(stderr,"P=%d\n",p);
	fprintf(stderr,"K=%d\n",k);
	fprintf(stderr,"TT=%d\n",TT);
	return 0;
}