#include <bits/stdc++.h>

using namespace std;

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

struct drumuri{
    int node, timp;
};

int n,m,k,p,x,y,z,drum[3520][200],amenda[3520][200];
bool ap[200][3520];
vector <drumuri> edges[200];
queue <int> q[3520];

void dial()
{
    q[0].push(1);
    for(int i=0; i<=3500; i++)
        while(!q[i].empty())
        {
            int x=q[i].front(); q[i].pop();
            for(auto y:edges[x])
                if(i+y.timp<=3500 and drum[i+y.timp][y.node]<=drum[i][x]+amenda[i][x])
                {
                    drum[i+y.timp][y.node]=drum[i][x]+amenda[i][x];
                    if(ap[y.node][i+y.timp]==0)
                        ap[y.node][i+y.timp]=1, q[i+y.timp].push(y.node);
                }
        }
}

int main()
{
    f>>n>>m>>k>>p;
    for(int i=1; i<=m; i++)
        f>>x>>y>>z, edges[x].push_back({y,z}), edges[y].push_back({x,z});
    for(int i=1; i<=n; i++)
        edges[i].push_back({i,1});
    for(int i=1; i<=k; i++)
        f>>x>>y>>z, amenda[y][x]+=z;
    dial();
    for(int i=1; i<=p; i++)
        f>>x>>y, g<<drum[y][x]+amenda[y][x]<<'\n';
    return 0;
}