#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int N = 50005, LOG = 18, INF = 1e9;
int k, n, m, q, dp[N][LOG][5][5], ans[5][5], tmp[5][5];
signed main() {
cin >> k >> n >> m >> q;
int bl = (n + k - 1) / k;
for(int i = 0; i < bl; i++){
for(int j = 0; j < LOG; j++){
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
dp[i][j][x][y] = INF;
}
}
}
}
for(int i = 0; i < m; i++){
int a, b, t;
cin >> a >> b >> t;
dp[a / k][0][a % k][b % k] = min(dp[a / k][0][a % k][b % k], t);
}
for(int j = 1; j < LOG; j++){
for(int i = 0; i + (1 << j) < bl; i++){
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
dp[i][j][x][y] = INF;
for(int z = 0; z < k; z++){
dp[i][j][x][y] = min(dp[i][j][x][y],
dp[i][j - 1][x][z] + dp[i + (1 << (j - 1))][j - 1][z][y]);
}
}
}
}
}
while(q--){
int a, b; cin >> a >> b;
int cur = a / k, tar = b / k;
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
ans[x][y] = INF;
}
}
for(int x = 0; x < k; x++) ans[x][x] = 0;
for(int j = LOG - 1; j >= 0; j--){
if(cur + (1 << j) <= tar){
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
tmp[x][y] = INF;
}
}
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
for(int z = 0; z < k; z++){
tmp[x][y] = min(tmp[x][y], ans[x][z] + dp[cur][j][z][y]);
}
}
}
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
ans[x][y] = tmp[x][y];
}
}
cur += (1 << j);
}
}
if(ans[a % k][b % k] >= INF) cout << -1 << endl;
else cout << ans[a % k][b % k] << endl;
}
}
