#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
const int N = 5e5 + 5, K = 5, INF = 6e8;
int w[N][K][K];
int n, m, k, o;
struct Node {
int w[K][K];
void fill(int val) {
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
w[i][j] = val;
}
}
}
} t[N * 4];
Node mrg(Node a, Node b, int w[K][K]) {
Node res;
res.fill(INF);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
for (int x = 0; x < k; x++) {
for (int y = 0; y < k; y++) {
res.w[i][y] = min(res.w[i][y], a.w[i][j] + w[j][x] + b.w[x][y]);
}
}
}
}
// for (int i = 0; i < k; i++) {
// for (int j = 0; j < k; j++) {
// cout << i << " " << j << " " << a.w[i][j] << "\n";
// }
// }
// cout << "\n";
// for (int i = 0; i < k; i++) {
// for (int j = 0; j < k; j++) {
// cout << i << " " << j << " " << b.w[i][j] << "\n";
// }
// }
// cout << "\n";
// for (int i = 0; i < k; i++) {
// for (int j = 0; j < k; j++) {
// cout << i << " " << j << " " << res.w[i][j] << "\n";
// }
// }
// cout << "\n";
// for (int i = 0; i < k; i++) {
// for (int j = 0; j < k; j++) {
// cout << i << " " << j << " " << w[i][j] << "\n";
// }
// }
// cout << "\n";
// cout << "\n";
return res;
}
void build(int v, int L, int R) {
if (L == R) {
t[v].fill(INF);
for (int i = 0; i < k; i++)
t[v].w[i][i] = 0;
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
t[v] = mrg(t[v * 2], t[v * 2 + 1], w[m]);
}
}
Node que(int l, int r, int v, int L, int R) {
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
if (r <= m)
return que(l, min(m, r), v * 2, L, m);
if (l > m)
return que(max(m + 1, l), r, v * 2 + 1, m + 1, R);
return mrg(que(l, min(m, r), v * 2, L, m),
que(max(m + 1, l), r, v * 2 + 1, m + 1, R), w[m]);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> k >> n >> m >> o;
int ctb = (n - 1) / k + 1;
for (int i = 0; i < ctb; i++) {
for (int x = 0; x < k; x++) {
for (int y = 0; y < k; y++) {
w[i][x][y] = INF;
}
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
int p = a / k;
a %= k;
b %= k;
w[p][a][b] = min(w[p][a][b], c);
// cout << p << " " << a << " " << b << " " << c << "\n";
}
build(1, 0, ctb - 1);
for (int i = 0; i < o; i++) {
int a, b;
cin >> a >> b;
int x = a / k,
y = b / k;
if (x == y) {
cout << "-1\n";
}
else {
Node res = que(x, y, 1, 0, ctb - 1);
int ans = res.w[a % k][b % k];
cout << (ans < INF ? ans : -1) << "\n";
// for (int i = 0; i < k; i++) {
// for (int j = 0; j < k; j++) {
// cout << i << " " << j << " " << res.w[i][j] << "\n";
// }
// }
}
}
return 0;
}
