#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 5e4 + 4;
const int B = 700;
int n, m, k, q;
int cost[maxn][5][5];
vector<int> dist[maxn / B + 5][B][5];
void minimize(int &x, int y) {
if (x > y) x = y;
}
void solve() {
cin >> k >> n >> m >> q;
memset(cost, 0x3f, sizeof(cost));
for (int i = 1; i <= m; ++i) {
int u, v, w; cin >> u >> v >> w;
cost[v / k][v % k][u % k] = w;
}
int nb = n / k;
for (int i = 0; i <= nb / B + 2; ++i) {
for (int j = 0; j < B; ++j) {
for (int c = 0; c < k; ++c) {
dist[i][j][c].resize(k, 1e9);
}
}
}
for (int bl = 0; bl <= nb / B; ++bl) {
int en = min((bl + 1) * B - 1, nb);
for (int c = 0; c < k; ++c) {
dist[bl][en % B][c][c] = 0;
}
for (int j = en; j > bl * B; --j) {
for (int c = 0; c < k; ++c) {
for (int x = 0; x < k; ++x) {
for (int y = 0; y < k; ++y) {
minimize(dist[bl][(j - 1) % B][c][y], dist[bl][j % B][c][x] + cost[j][x][y]);
}
}
}
}
}
while (q--) {
int s, t; cin >> s >> t;
int bs = s / k, bt = t / k;
if (bs >= bt) {
cout << (s == t ? 0 : -1) << '\n';
continue;
}
auto calc = [&](int s, int t) {
vector<int> f(k, 1e9);
f[t % k] = 0;
for (int i = t / k; i > s / k; --i) {
vector<int> nf(k, 1e9);
for (int j = 0; j < k; ++j) {
for (int c = 0; c < k; ++c) {
nf[c] = min(nf[c], f[j] + cost[i][j][c]);
}
}
f.swap(nf);
}
return f;
};
if (bs / B == bt / B) {
vector<int> f = calc(s, t);
cout << (f[s % k] == 1e9 ? -1 : f[s % k]) << '\n';
continue;
}
vector<int> f(k, 1e9);
for (int i = 0; i < k; ++i) {
f[i] = dist[bs / B][bs % B][i][s % k];
}
// debug(f);
for (int bl = bs / B + 1; bl < bt / B; ++bl) {
vector<int> nf(k, 1e9);
vector<vector<int>> d(k, vector<int>(k, 1e9));
for (int j = 0; j < k; ++j) {
d[j] = dist[bl][0][j];
}
// debug(bl, d);
for (int c = 0; c < k; ++c) {
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
if (max({d[c][i], f[j], cost[bl * B][i][j]}) < 1e9) {
nf[c] = min(nf[c], d[c][i] + f[j] + cost[bl * B][i][j]);
}
}
}
}
nf.swap(f);
}
int fb = bt / B * B;
vector<int> d = calc(fb * k, t);
// debug(d, f, fb * k);
int mn = 1e9;
for (int i = 0; i < k; ++i) {
for (int j = 0; j < k; ++j) {
if (max({cost[fb][i][j], d[i], f[j]}) < 1e9) {
mn = min(mn, d[i] + f[j] + cost[fb][i][j]);
}
}
}
cout << (mn == 1e9 ? -1 : mn) << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
/*
3 14 5 5
0 5 9
5 8 10
0 3 7
7 9 8
4 7 10
0 12
0 5
0 7
7 12
0 3
*/
