#include <fstream>

using namespace std;

ifstream cin("amenzi.in");
ofstream cout("amenzi.out");

#define NMAX 151
#define TMAX 3500
#define INF 1000000

int pr[NMAX][TMAX],dist[NMAX][NMAX],dp[NMAX][TMAX];
bool canReach[NMAX][TMAX];
int N,M,K,P;

void RoyFloyd()
{
    int i,j,k;

    for(k=1; k<=N; k++)
        for(i=1; i<=N; i++)
            for(j=1; j<=N; j++)
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}

void afis()
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        for(j=0;j<=22;j++)
            cout<<dp[i][j]<<" ";
        cout<<endl;
    }
}

int main()
{
    int i,j,k,a,b,c;

    cin>>N>>M>>K>>P;

    for(i=1; i<=N; i++)
    {
        for(j=1; j<=N; j++)
            dist[i][j]=INF;
        dist[i][i]=0;
    }
    for(i=1; i<=N; i++)
        for(j=1; j<=TMAX;j++)
            dp[i][j]=-INF;
    dp[1][0]=0;

    for(i=1; i<=M; i++)
    {
        cin>>a>>b>>c;
        dist[a][b]=c;
        dist[b][a]=c;
    }

    RoyFloyd();

    for(i=1; i<=K; i++)
    {
        cin>>a>>b>>c;
        pr[a][b]+=c;
    }

    /// SOLVE
    canReach[1][0]=true;
    for(j=0; j<=TMAX;j++)
        for(i=1; i<=N; i++)
        {
            if(j>0 &&canReach[i][j-1]==true)
            {
                dp[i][j]=max(dp[i][j],dp[i][j-1]);
                canReach[i][j]=true;
            }
            if(canReach[i][j])
            {
                for(k=1; k<=N; k++)
                {
                    int timp = dist[i][k];
                    if(j+timp<TMAX && i!=k)
                    {
                        dp[k][j+timp]=max(dp[k][j+timp],dp[i][j]+pr[k][j+timp]);
                        canReach[k][j+timp]=true;
                    }
                }
            }
        }

    for(i=1; i<=P; i++)
    {
        cin>>a>>b;
        cout<<dp[a][b]<<'\n';
    }
    //afis();
    return 0;
}