#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 150;
const int TMAX = 3500;

int dp[NMAX + 1][TMAX + 1];//val maxima de amenzi pt nodul i la momentul j 
vector<pair<int, int>> adj[NMAX + 1];
int n, m, k, p;
int amenda[NMAX + 1][TMAX + 1];

priority_queue<pair<int, pair<int, int>>> pq;

void dijkstra(int nod){
    
    dp[nod][0] = 0;
    pq.push({0, {nod, 0}});
    
    while(!pq.empty()){
        
        int maxval = pq.top().first;
        int fromnod = pq.top().second.first;
        int fromtimp = pq.top().second.second;
        
        pq.pop();
        
        if(maxval < dp[fromnod][fromtimp])
            continue;
            
        for(auto next : adj[fromnod]){
            
            int tonod = next.first;
            int tocost = next.second;
            
            if(tocost + fromtimp <= TMAX){
                
                if(dp[tonod][tocost + fromtimp] < dp[fromnod][fromtimp] + amenda[tonod][fromtimp + tocost]){
                    
                    dp[tonod][tocost + fromtimp] = dp[fromnod][fromtimp] + amenda[tonod][fromtimp + tocost];
                    pq.push({dp[tonod][tocost + fromtimp],{tonod, tocost + fromtimp}});
                    
                }
                
            }
            
        }
        
    }
    
}

int main()
{
    
    f >> n >> m >> k >> p;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        adj[y].push_back({x, cost});
        
    }
    
    for(int i=1; i<=k; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        amenda[x][y] = cost;
        
    }
    
    dijkstra(1);
    
    for(int i=1; i<=p; i++){
        
        int x, y;
        f >> x >> y;
        
        g << dp[x][y] << "\n";
        
    }

    return 0;
}