#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("amenzi.in");
ofstream cout("amenzi.out");
const int Tmp = 3501;
const int Nmax = 151;
int dp[Nmax][Tmp], cost[Nmax][Tmp];
int n, m, k, p, x, y, z;
vector<vector<pair<int, int>>> graf;
int main()
{
    cin >> n >> m >> k >> p;
    graf.assign(n+1, vector<pair<int, int>>());
    for(int i=1; i<=m; i++)
    {
        cin >> x >> y >> z;
        graf[x].push_back({y, z});
        graf[y].push_back({x, z});
    }
    for(int i=1; i<=n; i++)
        graf[i].push_back({i, 1});
    for(int i=1; i<=k; i++)
    {
        cin >> x >> y >> z;
        cost[x][y] += z;
    }
    for(int i=1; i<=n; i++)
        for(int j=0; j<Tmp; j++)
            dp[i][j] = -1;
    dp[1][0] = 0;
    for(int t=0; t<Tmp; t++)
        for(int node = 1; node <=n; node++)
            if(dp[node][t] != -1)
                for(auto next:graf[node])
                    if(t + next.second < Tmp && dp[next.first][t + next.second] <= dp[node][t] + cost[next.first][t + next.second])
                        dp[next.first][t + next.second] = dp[node][t] + cost[next.first][t + next.second];
    for(int i=1; i<=p; i++)
    {
        cin >> x >> y;
        cout << dp[x][y] << '\n';
    }
    return 0;
}