#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<long,long>>> vec;
vector<vector<long>> dis;
vector<bool> vis;
long raiz;
void bfs(int nodo)
{
priority_queue<pair<long,long>> cola;
cola.push({0,nodo});
dis[nodo][nodo]=0;
raiz=nodo;
while(!cola.empty())
{
nodo=cola.top().second;
cola.pop();
if(!vis[nodo]){
for(pair<long,long> next:vec[nodo]) {
if(dis[raiz][nodo]+next.second<dis[raiz][next.first]){
dis[raiz][next.first]=dis[raiz][nodo]+next.second;
cola.push({-dis[raiz][next.first],next.first});
}
}
vis[nodo]=true;
}
}
}
void solve()
{
long k,n,m,o; cin>>k>>n>>m>>o;
vec.assign(n,vector<pair<long,long>> ());
vis.assign(n,false);
dis.assign(n,vector<long> (n,1e6+1));
long a,b,t,p,g;
while(m--)
{
cin>>a>>b>>t;
if(b/k==(a/k)+1)
vec[a].push_back({b,t});
}
while(o--){
cin>>p>>g;
if(dis[p][p]!=0) bfs(p);
if(dis[p][g]==1e6+1) cout<<"-1"<<endl;
else cout<<dis[p][g]<<endl;
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
solve();
}
