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