#include <bits/stdc++.h>
#define l long long
using namespace std;
struct LayerConnnection {
l startlayer, endlayer;
array<array<l, 5>, 5> min_weights;
};
l k, n, m, q;
const l LEN = 50005;
const l INF = 1LL<<60;
array<vector<pair<l, l>>, LEN> adj;
array<array<l, 20>, LEN> adj_matrix;
array<LayerConnnection, LEN*4+10> tree;
LayerConnnection build_tree(l i, l s, l f) {
for (int a = 0; a < 5; a++) tree[i].min_weights[a].fill(INF);
tree[i].startlayer = s;
tree[i].endlayer = f;
if (s == f) {
for (int a = 0; a < k; a++) tree[i].min_weights[a][a] = 0;
return tree[i];
}
LayerConnnection left = build_tree(i*2, s, (s+f)/2);
LayerConnnection right = build_tree(i*2+1, (s+f)/2+1, f);
for (int a = 0; a < k; a++) {
for (int b = 0; b < k; b++) {
for (int c = 0; c < k; c++) {
if (!adj_matrix[((s+f)/2-1)*k+b][c]) continue;
for (int d = 0; d < k; d++) {
tree[i].min_weights[a][d] = min(tree[i].min_weights[a][d], left.min_weights[a][b] + adj_matrix[((s+f)/2-1)*k+b][c] + right.min_weights[c][d]);
}
}
}
}
return tree[i];
}
LayerConnnection query_tree(l i, l s, l f, l a, l b) {
if (a > f || b < s) {
LayerConnnection node = {-1, -1};
return node;
}
if (a <= s && b >= f) return tree[i];
LayerConnnection node = {s, f};
for (int a = 0; a < k; a++) node.min_weights[a].fill(INF);
LayerConnnection left = query_tree(i*2, s, (s+f)/2, a, b);
LayerConnnection right = query_tree(i*2+1, (s+f)/2+1, f, a, b);
if (left.startlayer == -1) return right;
if (right.startlayer == -1) return left;
for (int a = 0; a < k; a++) {
for (int b = 0; b < k; b++) {
for (int c = 0; c < k; c++) {
if (!adj_matrix[((s+f)/2-1)*k+b][c]) continue;
for (int d = 0; d < k; d++) {
node.min_weights[a][d] = min(node.min_weights[a][d], left.min_weights[a][b] + adj_matrix[((s+f)/2-1)*k+b][c] + right.min_weights[c][d]);
}
}
}
}
return node;
}
int main() {
cin >> k >> n >> m >> q;
l a, b, w;
for (int i = m; i--;) {
cin >> a >> b >> w;
adj[a].push_back({b, w});
adj_matrix[a][b%k] = w;
}
build_tree(1, 1, n/k + 1);
LayerConnnection node;
while (q--) {
cin >> a >> b;
node = query_tree(1, 1, n/k+1, a/k+1, b/k+1);
if (node.min_weights[a%k][b%k] < (1LL<<58)) cout << node.min_weights[a%k][b%k] << endl;
else cout << -1 << endl;
}
return 0;
}
