#include <bits/stdc++.h>
#define long long long
using namespace std;
const int V = 50000, K = 16;
const int N = 5;
const int MAX = numeric_limits<int>::max();
struct Element {
int a[N][N];
int* operator [] (int i) {
return a[i];
}
Element() {
for (int i = 0; i < N; i++) {
fill(a[i], a[i] + N, MAX);
a[i][i] = 0;
}
}
};
Element operator + (Element &u, Element &v) {
Element w;
for (int i = 0; i < N; i++) {
fill(w[i], w[i] + N, MAX);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
if (u[i][k] < MAX && v[k][j] < MAX) {
w[i][j] = min(w[i][j], u[i][k] + v[k][j]);
}
}
}
}
return w;
}
int n, m, k, q;
Element f[K][V];
void solve() {
cin >> k >> n >> m >> q;
for (int u = 0; u < n / k; u++) {
for (int i = 0; i < N; i++) {
fill(f[0][u][i], f[0][u][i] + N, MAX);
}
}
for (int i = 0; i < m; i++) {
int u, v;
int w;
cin >> u >> v >> w;
f[0][u / k][u % k][v % k] = w;
}
for (int i = 0; i < K - 1; i++) {
for (int u = 0; u < n / k; u++) {
if (u + (1 << i) >= n / k) {
f[i + 1][u] = f[i][u];
} else {
f[i + 1][u] = f[i][u] + f[i][u + (1 << i)];
}
}
}
for (int i = 0; i < q; i++) {
int u, v;
cin >> u >> v;
int p = u / k;
Element x;
for (int j = K - 1; j >= 0; j--) {
if (p + (1 << j) <= v / k) {
x = x + f[j][p];
p = p + (1 << j);
}
}
if (x[u % k][v % k] < MAX) {
cout << x[u % k][v % k] << "\n";
} else {
cout << -1 << "\n";
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
