#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][6][50000];
for (int i = 0; i<2; i++){
for (int x = 0; x<k; x++){
for (int j = 0; j<n; j++){
distfrom[i][x][j]=INF;
}
}
}
vector<vector<pair<int,int>>> to(n);
int fromcnt[50000]={0};
int ans[10000];
for (int i = 0; i<o; i++){
int a,b;
cin>>a>>b;
ans[i]=-1;
//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%k][x]=0;
from.insert(x);
}
for (int j = 0; j<k; j++){
int ikj = i*k+j;
if (ikj>=n){break;}
for (int nf : from){
distfrom[curr][j][nf]=INF;
for (auto p : adjlist[ikj]){
distfrom[curr][j][nf]=min(distfrom[curr][j][nf],distfrom[!curr][p.first%k][nf]+p.second);
}
}
for (auto p : to[ikj]){
if (distfrom[curr][j][p.first]!=INF){
ans[p.second]=distfrom[curr][j][p.first];
}
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';
}
}
