#include <bits/stdc++.h>
using namespace std;
int n,m,K,p,i,j,k,t,l,d[3504][151],am[3504][151],a,b,c;
vector < pair <int,int> > v[151];
ifstream f("amenzi.in");
ofstream g("amenzi.out");
int main()
{
   f>>n>>m>>K>>p;
   for(i=1;i<=m;i++)
   {
       f>>a>>b>>c;
       v[a].push_back({b,c});
       v[b].push_back({a,c});
   }
   for(i=1;i<=K;i++)
   {
       f>>a>>b>>c;
       am[b][a]=c;
   }
   for(i=0;i<=3504;i++)
    for(j=1;j<=n;j++)
    d[i][j]=-1;
    d[0][1]=0;
   for(i=1;i<=3504;i++)
    for(j=1;j<=n;j++)
   {
       for(k=0;k<v[j].size();k++)
       {
           int t=v[j][k].second;
           int l=v[j][k].first;
           if(i-t>=0)
            d[i][j]=max(d[i][j],d[i-t][l]);
       }
       d[i][j]=max(d[i][j],d[i-1][j]);
       if(d[i][j]>=0)d[i][j]=d[i][j]+am[i][j];

   }
   for(i=0;i<=3501;i++)
   {
       for(j=1;j<=n;j++)
        g<<d[i][j]<<" ";
       g<<endl;
   }
   for(i=1;i<=p;i++)
   {
       f>>a>>b;
       g<<d[b][a]<<endl;
   }


    return 0;
}