#include <stdio.h>
#define N 50000
#define K 5
#define Q 10000
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int dd[N][K][K], ii[Q], jj[Q], ans[Q], k;
void solve(int *hh, int l, int r, int q) {
static int dd1[N][K][K], dd2[N][K][K];
int m, h, hl, hm, hr, i, j, a, b, c, tmp;
if (q == 0)
return;
m = (l + r) / 2;
hl = 0, hm = 0, hr = q;
while (hm < hr)
if (ii[hh[hm]] / k <= m && m <= jj[hh[hm]] / k)
hm++;
else if (jj[hh[hm]] / k < m) {
tmp = hh[hl], hh[hl] = hh[hm], hh[hm] = tmp;
hl++, hm++;
} else {
hr--;
tmp = hh[hm], hh[hm] = hh[hr], hh[hr] = tmp;
}
for (i = l; i <= m; i++)
for (a = 0; a < k; a++)
for (b = 0; b < k; b++)
dd1[i][a][b] = INF;
for (i = m; i <= r; i++)
for (a = 0; a < k; a++)
for (b = 0; b < k; b++)
dd2[i][a][b] = INF;
for (a = 0; a < k; a++)
dd1[m][a][a] = dd2[m][a][a] = 0;
for (i = m; i > l; i--)
for (a = 0; a < k; a++)
for (b = 0; b < k; b++) {
int x = dd1[i][a][b];
if (x != INF)
for (c = 0; c < k; c++)
dd1[i - 1][c][b] = min(dd1[i - 1][c][b], dd[i - 1][c][a] + x);
}
for (i = m; i < r; i++)
for (a = 0; a < k; a++)
for (b = 0; b < k; b++) {
int x = dd2[i][a][b];
if (x != INF)
for (c = 0; c < k; c++)
dd2[i + 1][a][c] = min(dd2[i + 1][a][c], x + dd[i][b][c]);
}
for (h = hl; h < hr; h++) {
int h_ = hh[h], x;
i = ii[h_] / k, a = ii[h_] % k, j = jj[h_] / k, b = jj[h_] % k;
x = INF;
for (c = 0; c < k; c++)
x = min(x, dd1[i][a][c] + dd2[j][c][b]);
ans[h_] = x;
}
solve(hh, l, m - 1, hl);
solve(hh + hr, m + 1, r, q - hr);
}
int main() {
static int hh[Q];
int n, m, q, h, i, j, a, b;
scanf("%d%d%d%d", &k, &n, &m, &q), n = (n + k - 1) / k;
for (i = 0; i + 1 < n; i++)
for (a = 0; a < k; a++)
for (b = 0; b < k; b++)
dd[i][a][b] = INF;
while (m--) {
int d;
scanf("%d%d%d", &i, &j, &d);
dd[i / k][i % k][j % k] = d;
}
for (h = 0; h < q; h++) {
scanf("%d%d", &ii[h], &jj[h]);
hh[h] = h;
}
solve(hh, 0, n - 1, q);
for (h = 0; h < q; h++)
printf("%d\n", ans[h] == INF ? -1 : ans[h]);
return 0;
}
