#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int n, m, q, k;
int a[50001];
vector<ii> adj[50001], adj_re[50001];
int val[20][50001][5][5];
int comb(int x, int y) {
return min(x, y); // Replace min with any associative operation
}
void init(int l, int r, int lev) {
if (l == r)
return;
int mi = (l + r) / 2;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++)
val[lev][mi][i][j] = 1e9;
val[lev][mi][i][i] = 0;
}
for (int i = mi - 1; i >= l; i--) {
for (int j = 0; j < k; j++) {
for (int z = 0 ; z < k; z++)
val[lev][i][j][z] = 1e9;
int u = i * k + j;
for (ii _ : adj[u]) {
int v = _.first, c = _.second;
int nxt = v % k;
for (int z = 0; z < k; z++)
val[lev][i][j][z] = comb(val[lev][i][j][z], val[lev][i + 1][nxt][z] + c);
}
}
}
for (int i = mi + 1; i <= r; i++) {
for (int j = 0; j < k; j++) {
for (int z = 0 ; z < k; z++)
val[lev][i][j][z] = 1e9;
int u = i * k + j;
for (ii _ : adj_re[u]) {
int v = _.first, c = _.second;
int nxt = v % k;
for (int z = 0; z < k; z++)
val[lev][i][j][z] = comb(val[lev][i - 1][nxt][z] + c, val[lev][i][j][z]);
}
}
}
if (r - l <= 1) return;
init(l, mi, lev + 1);
init(mi, r, lev + 1);
}
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> k >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v, c; cin >> u >> v >> c;
adj[u].push_back(ii(v, c));
adj_re[v].push_back(ii(u, c));
}
init(0, (n - 1)/k, 0);
while (q--) {
int u, v; cin >> u >> v;
int id1 = u / k, id2 = v / k;
if (id1 == id2) cout << -1 << '\n';
else {
int lev = 0;
int l = 0, r = (n - 1)/k;
while(1) {
int mi = (l + r) / 2;
if (id1 <= mi && mi <= id2) break;
else {
if (mi < id1) l = mi;
else r = mi;
lev++;
}
}
int ans = 1e9;
for (int i = 0; i < k; i++)
ans = min(ans, val[lev][id1][u % k][i] + val[lev][id2][v % k][i]);
if (ans >= 1e9) cout << -1 << '\n';
else cout << ans << '\n';
}
}
}
