#include <bits/stdc++.h>
using namespace std;
#define MAXN 50005
#define INF 1000000009
int ckmin(int &a, int b){return (b<a)?a=b:a;}
int ckmax(int &a, int b){return (b>a)?a=b:b;}
vector<pair<pair<int, int>, int>> adj[MAXN][5];
int p, n, m, q;
vector<pair<pair<int, int>, int>> queries;
int ans[MAXN];
int mxlvl;
void cdq(int l, int r, vector<pair<pair<int, int>, int>> &bruh){
if(r < l) return;
int mid = (l+r)/2;
int dp[r-l+1][p][p];
for(int i = l; i<=r; i++){
for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[i-l][a][b] = INF;
}
for(int a = 0; a<p; a++) for(int b = 0; b<p; b++) dp[mid-l][a][b] = (a == b)?0:INF;
for(int i = mid+1; i<=r; i++){
for(int a = 0; a<p; a++){
for(int b = 0; b<p; b++){
for(auto x : adj[i-1][b]) ckmin(dp[i-l][a][x.first.second], dp[i-1-l][a][b]+x.second);
}
}
}
for(int i = mid-1; i>=l; i--){
for(int a = 0; a<p; a++){
for(int b = 0; b<p; b++){
for(auto x : adj[i][a]) ckmin(dp[i-l][a][b], dp[i+1-l][x.first.second][b]+x.second);
}
}
}
vector<pair<pair<int, int>, int>> lqueries, rqueries;
for(auto x : bruh){
if(x.first.second/p < mid){
lqueries.push_back(x);
continue;
}
if(x.first.first/p > mid){
rqueries.push_back(x);
continue;
}
for(int y = 0; y<p; y++){
ckmin(ans[x.second], dp[x.first.first/p-l][x.first.first%p][y]+dp[x.first.second/p-l][y][x.first.second%p]);
}
}
cdq(l, mid-1, lqueries);
cdq(mid+1, r, rqueries);
}
int main(){
// freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> p >> n >> m >> q; mxlvl = n/p;
for(int i = 0; i<m; i++){
int a, b, w; cin >> a >> b >> w;
adj[a/p][a%p].push_back({{b/p, b%p}, w});
}
for(int i = 0; i<q; i++){
int a, b; cin >> a >> b;
queries.push_back({{a, b}, i});
}
fill(ans, ans+q, INF);
cdq(0, mxlvl, queries);
for(int i = 0; i<q; i++) cout << ((ans[i] == INF)?-1:ans[i]) << endl;
}
