#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], s[MAX];

struct crime{
       int t;
       int cost;
};
vector<vector<crime> > cr;
struct Comp{
       bool operator() (crime crima1, crime crima2)
       {
            return crima1.t < crima2.t;
       }
};
void DF(int i);
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";    
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= 50; j++)
            fout << a[i][j] << " ";
        fout << "\n";
    }
    fin.close();
    fout.close();
    
    return 0;
}

void Din()
{
    RF();
    
    int i;
    DF(1);
    /*for (i = 1; i <= n; i++)
        DF(i);
        */
}

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];
}

void DF(int i)
{
    int  j, k1;
    crime k2;
    vector<crime>::iterator crimes, final;
    s[i] = 1;
    for (j = 1; j <= n; j++)
          if (d[i][j] != INF && i != j && !s[j])
          {
                DF(j);      
                for (k1 = 1; k1 <= MAX_T-1; k1++)
                {
                    if (!cr[i].empty())
                    {
                         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;
                         }
                    }
                    else 
                    {
                         if (k1-d[i][j] >= 0 && a[i][k1] < a[j][k1-d[i][j]])   
                               a[i][k1] = a[j][k1-d[i][j]];
                    }
                }
          }
}