#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>> adjlist;
int INF = 1e9;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int k,n,m,o;
cin>>k>>n>>m>>o;
adjlist.resize((n/k)*k+k);
for (int i = 0; i<m; i++){
int a,b,t;
cin>>a>>b>>t;
adjlist[b].push_back({a,t});
}
unordered_set<int> from;
vector<vector<int>> addat(n/k+1);
//vector<vector<vector<int>>> distfrom(2,vector<vector<int>>(n,vector<int>(k,INF)));
int distfrom[2][50002][6];
for (int i = 0; i<2; i++){
for (int j = 0; j<n; j++){
for (int x = 0; x<k; x++){
distfrom[i][j][x]=INF;
}
}
}
vector<vector<pair<int,int>>> to(n);
vector<int> fromcnt(n,0);
vector<int> ans(o,-1);
for (int i = 0; i<o; i++){
int a,b;
cin>>a>>b;
//from.push_back(a);
addat[a/k].push_back(a);
to[b].push_back({a,i});
fromcnt[a]++;
}
//sort(from.begin(),from.end());
//from.erase(unique(from.begin(),from.end()),from.end());
bool curr = 0;
for (int i = 1; i<=(n/k+1); i++){
//cout<<i<<endl;
for (int x : addat[i-1]){
distfrom[!curr][x][x%k]=0;
from.insert(x);
}
for (int j = 0; j<k; j++){
if (i*k+j>=n){break;}
for (int nf : from){
distfrom[curr][nf][j]=INF;
for (auto p : adjlist[i*k+j]){
distfrom[curr][nf][j]=min(distfrom[curr][nf][j],distfrom[!curr][nf][p.first%k]+p.second);
}
}
for (auto p : to[i*k+j]){
if (distfrom[curr][p.first][j]!=INF){
ans[p.second]=distfrom[curr][p.first][j];
}
fromcnt[p.first]--;
if (fromcnt[p.first]==0){
from.erase(p.first);
}
}
}
curr=!curr;
}
for (int i = 0; i<o; i++){
cout<<ans[i]<<'\n';
}
}
