#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 5e4 + 50;
const ll inf = 1e10;
vector<vector<ll>> dat[20][N];
ll mask[N];
vector<array<int, 3>> G[N];
int k, n, m, q;
vector<vector<ll>> I() {
vector<vector<ll>> res(k, vector<ll>(k, inf));
for (int i = 0; i < k; i++) res[i][i] = 0;
return res;
}
void divide(int l, int r, int lvl) {
if (l == r) return;
int m = (r + l) / 2;
dat[lvl][m] = I();
for (int i = m - 1; i >= l; i--) {
dat[lvl][i].assign(k, vector<ll>(k, inf));
for (int x = 0; x < k; x++) {
for (auto u : G[i]) {
dat[lvl][i][u[0]][x] = min(dat[lvl][i][u[0]][x], dat[lvl][i + 1][u[1]][x] + u[2]);
}
}
}
for (int i = m + 1; i <= r; i++) {
dat[lvl][i].assign(k, vector<ll>(k, inf));
for (int x = 0; x < k; x++) {
for (auto u : G[i - 1]) {
dat[lvl][i][u[1]][x] = min(dat[lvl][i][u[1]][x], dat[lvl][i - 1][u[0]][x] + u[2]);
}
}
}
for (int i = m + 1; i <= r; i++) mask[i] ^= (1 << lvl);
divide(l, m, lvl + 1); divide(m + 1, r, lvl + 1);
}
int main()
{
// ifstream cin("input.txt");
// ofstream cout("output.txt");
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> k >> n >> m >> q;
n = (n + k - 1) / k * k;
for (int i = 0; i < m; i++) {
int a, b, t; cin >> a >> b >> t;
G[a / k].push_back({a % k, b % k, t});
}
divide(0, n / k - 1, 0);
while(q--) {
int a, b; cin >> a >> b;
if (a / k == b / k) {
cout << "-1\n";
} else {
int lvl = __builtin_ctz(mask[a / k] ^ mask[b / k]);
ll ans = inf;
for (int x = 0; x < k; x++) ans = min(ans, dat[lvl][a / k][a % k][x] + dat[lvl][b / k][b % k][x]);
cout << (ans == inf ? -1 : ans) << '\n';
}
}
}
