#include <fstream>
#include <vector>
#define INF 9999999
#define MAX 151
#define MAX_T 3501

using namespace std;

int n, m, k, p;
int d[MAX][MAX], a[MAX][MAX_T];

struct crime{
       int t;
       int cost;
};
vector<vector<crime> > cr;
struct Comp{
       bool operator() (crime crima1, crime crima2)
       {
            return crima1.t < crima2.t;
       }
};

void Din();
void RF();

int main()
{
    crime aux;
    int i, j, place, v1, v2, c;
    
    ifstream fin("amenzi.in");
    ofstream fout("amenzi.out");
    
    fin >> n >> m >> k >> p;
    cr.resize(n+3);
    
    for (i = 1; i <= n; i++)   
    { 
        d[i][i] = 0;
        for (j = i+1; j <= n; j++)
            d[i][j] = d[j][i] = INF;
    }
    for (i = 1; i <= m; i++)    
    {
        fin >> v1 >> v2 >> c;
        d[v1][v2] = d[v2][v1] = c;    
    }
    for (i = 1; i <= k; i++)
    {
        fin >> place >> aux.t >> aux.cost;
        cr[place].push_back(aux);
        a[place][aux.t] = aux.cost;
    }
    for (i = 1; i <= n; i++)
        sort(cr[i].begin(), cr[i].end(), Comp());
        
    Din();
    
    for (i = 1; i <= p; i++)
    {
        fin >> v1 >> v2;
        fout << a[v1][v2] << "\n";    
    }
    fin.close();
    fout.close();
    
    return 0;
}

void Din()
{
    RF();
    
    int i, j, k1;
    crime k2;
    vector<crime>::iterator crimes, final;
    
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (d[i][j] != INF && i != j)
                for (k1 = 1; k1 <= MAX_T-1; k1++)
                {
                    a[i][k1] = a[i][k1-1];
                    for (crimes = cr[i].begin(), final = cr[i].end(); crimes != final; crimes++)
                    {
                         k2 = *crimes;
                         if (k1-d[i][j]-k2.t >= 0 && a[i][k1] < a[j][k1-d[i][j]-k2.t]+k2.cost)   
                               a[i][k1] = a[j][k1-d[i][j]-k2.t]+k2.cost;
                    }
                }
}

void RF()
{
    int i, j, k;
    for (k = 1; k <= n; k++)     
        for (i = 1; i <= n; i++)
            for (j = 1;j <= n; j++)
                if (d[i][j] > d[i][k] + d[k][j])
                    d[i][j] = d[i][k] + d[k][j];
}