#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()
const int LG = 17, MAXK = 5, MX = 5e4, inf = 0x3f;
int dp[MX][LG][MAXK][MAXK], ans[MAXK][MAXK], temp[MAXK][MAXK], k;
inline void combine(int target[MAXK][MAXK], int a[MAXK][MAXK], int b[MAXK][MAXK]){
for(int x = 0; x < k; x++){
for(int y = 0; y < k; y++){
for(int z = 0; z < k; z++){
target[x][y] = min(target[x][y], a[x][z] + b[z][y]);
}
}
}
}
void solve(){
int n, m, o, a, b, t;
cin >> k >> n >> m >> o;
memset(dp, inf, sizeof(dp));
while(m--){
cin >> a >> b >> t;
dp[a / k][0][a % k][b % k] = t;
}
for(int j = 1; j < LG; j++){
for(int i = 0; i + (1ll << j) < (n + k - 1) / k; i++){
combine(dp[i][j], dp[i][j - 1], dp[i + (1ll << (j - 1))][j - 1]);
}
}
while(o--){
cin >> a >> b;
memset(ans, inf, sizeof(ans));
for(int i = 0; i < MAXK; i++) ans[i][i] = 0;
for(int cur = a / k, dest = b / k, i = LG - 1; ~i; i--){
if(cur + (1ll << i) <= dest){
memset(temp, inf, sizeof(temp));
combine(temp, ans, dp[cur][i]);
memcpy(ans, temp, sizeof(ans));
cur += (1ll << i);
}
}
cout << (ans[a % k][b % k] == 0x3f3f3f3f ? -1 : ans[a % k][b % k]) << "\n";
}
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
