// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 5e4 + 10, MOD = 1e9 + 7;
int M[N], dp[18][5][N], n, k, q, m; vector<pii> in[N], out[N];
void divide(int l = 0, int r = (n - 1) / k + 1, int h = 0) {
if (r - l < 3) return;
int mid = (l + r) >> 1;
//printf("l %d mid %d r %d\n", l, mid, r);
for (int i = mid * k; i < mid * k + k; i++) dp[h][i % k][i] = 0;
for (int i = mid * k - 1; i >= l * k; i--) {
for (int j = 0; j < k; j++) for (pii u : out[i]) {
dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S);
}
}
for (int i = mid * k + k; i < min(n, r * k); i++) {
for (int j = 0; j < k; j++) for (pii u : in[i]) {
dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S);
}
}
for (int i = mid; i < r; i++) M[i] ^= 1 << h;
divide(l, mid, h + 1), divide(mid, r, h + 1);
}
int main() {
for (int i = 0; i < 18; i++) for (int j = 0; j < 5; j++) fill(dp[i][j], dp[i][j] + N, MOD);
scanf("%d%d%d%d", &k, &n, &m, &q);
for (int i = 0; i < m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
out[u].push_back({v, w});
in[v].push_back({u, w});
}
divide();
for (; q; q--) {
int a, b; scanf("%d%d", &a, &b);
if (a == b) printf("%d\n", 0);
else if (a / k == b / k) printf("-1\n");
else if (b / k - a / k == 1) {
int ret = -1;
for (pii u : out[a]) if (u.F == b) ret = u.S;
printf("%d\n", ret);
} else {
if (M[a / k] == M[b / k]) {
printf("%d %d\n", a / k, b / k);
exit(0);
}
int h = __builtin_ctz(M[a / k] ^ M[b / k]);
int ret = MOD;
for (int i = 0; i < 5; i++) {
ret = min(ret, dp[h][i][a] + dp[h][i][b]);
}
printf("%d\n", ret == MOD ? -1 : ret);
}
}
return 0;
}
