#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int K, N, M, O;
cin >> K >> N >> M >> O;
while (N % K != 0) N += 1;
const int INF = 1e9;
vector<array<array<int, 5>, 5>> A(N / K);
for (int i = 0; i < N / K; i++) {
for (int x = 0; x < K; x++) {
for (int y = 0; y < K; y++) {
A[i][x][y] = INF;
}
}
}
while (M--) {
int a, b, t;
cin >> a >> b >> t;
assert(a / K + 1 == b / K);
A[a / K][a % K][b % K] = min(A[a / K][a % K][b % K], t);
}
vector<array<array<int, 5>, 5>> tree(N / K * 2);
const auto Merge = [&](array<array<int, 5>, 5> p, array<array<int, 5>, 5> q) {
array<array<int, 5>, 5> res;
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
res[i][j] = INF;
for (int k = 0; k < K; k++) {
res[i][j] = min(res[i][j], p[i][k] + q[k][j]);
}
}
}
return res;
};
for (int i = 0; i < N / K; i++) {
tree[i + N / K] = A[i];
}
for (int i = N / K - 1; i > 0; i--) {
tree[i] = Merge(tree[i * 2], tree[i * 2 + 1]);
}
const auto Query = [&](int l, int r) {
array<array<int, 5>, 5> lft;
array<array<int, 5>, 5> rgt;
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
lft[i][j] = i == j ? 0 : INF;
rgt[i][j] = i == j ? 0 : INF;
}
}
for (l += N / K, r += N / K; l < r; l /= 2, r /= 2) {
if (l & 1) lft = Merge(lft, tree[l++]);
if (r & 1) rgt = Merge(tree[--r], rgt);
}
return Merge(lft, rgt);
};
while (O--) {
int a, b;
cin >> a >> b;
if (b / K <= a / K) {
cout << -1 << '\n';
continue;
}
assert(a / K + 1 <= b / K);
int ans = Query(a / K, b / K)[a % K][b % K];
if (ans == INF) {
cout << -1 << '\n';
} else {
cout << ans << '\n';
}
}
return 0;
}
