#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 inf = 1ll << 40;
int K;
struct node {
std::vector<std::vector<i64>> cost;
node() : cost(K, std::vector(K, inf)) {
for (int i = 0; i < K; ++i) {
cost[i][i] = 0;
}
}
void fill_inf() {
std::fill(cost.begin(), cost.end(), std::vector(K, inf));
}
};
node operate(const node &a, const node &b) {
const int w = K;
node res;
res.fill_inf();
for (int i = 0; i < w; ++i) {
for (int j = 0; j < w; ++j) {
for (int k = 0; k < w; ++k) {
res.cost[i][k] = std::min(res.cost[i][k], a.cost[i][j] + b.cost[j][k]);
}
}
}
return res;
// O(K^3)
}
struct segment_tree {
int n, size;
std::vector<node> tree;
void update(const int i) {
tree[i] = operate(tree[2 * i], tree[2 * i + 1]);
}
segment_tree(const std::vector<node> &data) : n((int)data.size()) {
size = 1;
while (size < n) {
size *= 2;
}
tree.resize(2 * size);
for (int i = 0; i < n; ++i) {
tree[i + size] = data[i];
}
for (int i = size - 1; i >= 1; --i) {
update(i);
}
}
node fold(int l, int r) {
node pl, pr;
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l & 1) {
pl = operate(pl, tree[l++]);
}
if (r & 1) {
pr = operate(tree[--r], pr);
}
}
return operate(pl, pr);
}
};
int main() {
int N, M, O;
std::cin >> K >> N >> M >> O;
std::vector<int> A(M), B(M);
std::vector<i64> T(M);
for (int i = 0; i < M; ++i) {
std::cin >> A[i] >> B[i] >> T[i];
}
std::vector<int> X(O), Y(O);
for (int i = 0; i < O; ++i) {
std::cin >> X[i] >> Y[i];
}
const int W = (N + K - 1) / K;
std::vector<node> cost_table(W - 1);
for (auto &e : cost_table) {
e.fill_inf();
}
for (int i = 0; i < M; ++i) {
const int p = A[i] / K;
cost_table[p].cost[A[i] % K][B[i] % K] = T[i];
}
segment_tree seg(cost_table);
for (int i = 0; i < O; ++i) {
const int l = X[i] / K, r = Y[i] / K;
const auto res = seg.fold(l, r);
i64 ans = res.cost[X[i] % K][Y[i] % K];
if (ans >= inf) {
ans = -1;
}
std::cout << ans << std::endl;
}
}
