#include<fstream>
#include<vector>

using namespace std;

#define max_t 3501
#define max_n 155

ifstream f("amenzi.in");
ofstream g("amenzi.out");

struct muchie{
	int x;
	int c;
}mc;

int a , b , c , nod2 , cost , n , m , k , p;
int A[max_n][max_t] , D[max_n][max_t];
vector<muchie>L[max_n];

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

void read(){
	
	f>>n>>m>>k>>p;
	
	for(int i = 1 ; i <= m ; i++){
		f>>a>>b>>mc.c;
		mc.x = b; L[a].push_back(mc);
		mc.x = a; L[b].push_back(mc);
	}
	
	for(int i = 1 ; i <= k ; i++){
		f>>a>>b>>c;
		A[a][b] = c;
	}
	
}

void initializare(){
	
	for(int i = 1 ; i <= n ; i++)
		for(int j = 0 ; j < max_t ; j++)
			D[i][j] = -1;
	
	D[1][0] = 0;
}

void solve(){
	
	for(int j = 0 , i , k ; j <= max_t ; j++){
		for(i = 1 ; i < n ; i++){
			
			if( D[i][j] == (-1) )  continue;
			
			D[i][j] = maxim(D[i][j] , D[i][j-1]);
			
			D[i][j] += A[i][j];
			
			for(k = 0 ; k < L[i].size() ; k++){
				nod2 = L[i][k].x;
				cost = L[i][k].c;
				D[nod2][j+cost] = maxim(D[nod2][j+cost] , D[i][j]);
			}
			
		}
	}
	
}

void print(){
	
	for(int i = 1 ; i <= p ; i++){
		f>>a>>b;
		g<<D[a][b]<<"\n";
	}
	
}

int main(){
	
	read(); 
	initializare();  
	solve(); 
	print();
	
	return 0;
}