#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 155;
const int TMAX = 3501;

int mat[NMAX][TMAX],n,m,K,p;
int dp[NMAX][TMAX];
string s;
vector < pair < int, int > > v[NMAX];

int made(int &lo, int &hi){
    int x = 0;
    for(int i = lo ; i <= hi ; i++)
        x = x * 10 + s[i] - '0';
    return x;
}

int main(){
    int i,j,x,y,z,lo;
    f >> n >> m >> K >> p;
    getline(f,s);
    for(i = 1 ; i <= m ; i++){

        getline(f,s);

        x = y = z = 0;
        for(j = 0 ; j < s.size() ; j++)
            if(s[j] >= '0' && s[j] <= '9'){
                lo = j;
                j++;
                while(s[j] >= '0' && s[j] <= '9' && j < s.size())
                    j++;
                j--;
                if(!x)
                    x = made(lo, j);
                else
                    if(!y)
                        y = made(lo, j);
                    else
                        z = made(lo, j);
            }

        v[x].push_back(make_pair(y,z));
        v[y].push_back(make_pair(x,z));
    }

    for(i = 1 ; i <= K ; i++){
        getline(f,s);

        x = y = z = 0;
        for(j = 0 ; j < s.size() ; j++)
            if(s[j] >= '0' && s[j] <= '9'){
                lo = j;
                j++;
                while(s[j] >= '0' && s[j] <= '9' && j < s.size())
                    j++;
                j--;
                if(!x)
                    x = made(lo, j);
                else
                    if(!y)
                        y = made(lo, j);
                    else
                        z = made(lo, j);
            }
        mat[x][y] += z;
    }

    for(i = 0 ; i < 3501 ; i++)
        for(j = 0 ; j <= n ; j++)
            dp[j][i] = -1;

    dp[1][0] = mat[1][0];
    for(i = 1 ; i < 3501 ; i++)
        for(j = 1 ; j <= n ; j++){

            dp[j][i] = dp[j][i - 1];

            for(auto it: v[j]){

                if(i >= it.second)
                    dp[j][i] = max(dp[j][i], dp[it.first][i - it.second]);

            }
            if(dp[j][i] != -1)
                dp[j][i] += mat[j][i];
        }

    for(i = 1 ; i <= p ; i++){
        getline(f,s);

        x = y = 0;
        for(j = 0 ; j < s.size() ; j++)
            if(s[j] >= '0' && s[j] <= '9'){
                lo = j;
                j++;
                while(s[j] >= '0' && s[j] <= '9' && j < s.size())
                    j++;
                j--;
                if(!x)
                    x = made(lo, j);
                else
                    y = made(lo, j);

            }
        g << dp[x][y] << "\n";
    }

    return 0;
}