#include <bits/stdc++.h>
using namespace std;
const int N = 50'000 + 10,
S = 400;
int k, n, m, q;
vector<pair<int, int>> ad[N];
void preSktra(int st, vector<int>& f) {
f = vector<int>(n + 1, 1'000'000'000);
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<>> q;
q.push({f[st] = 0, st});
while (q.size()) {
auto [d, u] = q.top(); q.pop();
if (d != f[u]) continue;
for (const auto& [v, w] : ad[u]) {
if (f[v] > d + w) q.push({f[v] = d + w, v});
}
}
}
int id[N], rvs[N], it;
vector<int> pF[S + 10];
int f[N];
int sktra(int st, int ed) {
int ret = 1'000'000'000;
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<>> q;
q.push({f[st] = 0, st});
vector<int> vt;
while (q.size()) {
auto [d, u] = q.top(); q.pop();
vt.push_back(u);
if (d != f[u]) continue;
if (id[u]) {
ret = min(ret, f[u] + pF[id[u]][ed]);
continue;
}
for (const auto& [v, w] : ad[u]) {
if (f[v] > d + w) q.push({f[v] = d + w, v});
}
}
ret = min(ret, f[ed]);
for (const auto& i : vt) f[i] = 1'000'000'000;
return ret >= 1'000'000'000 ? -1 : ret;
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> k >> n >> m >> q;
for (int i = 1; i <= m; ++i) {
int u, v, w; cin >> u >> v >> w;
ad[u].push_back({v, w});
}
for (int i = 0; i < n; ++i) {
if ((i / k) % S == 0) preSktra(i, pF[id[i] = ++it]);
}
memset(f, 63, sizeof f);
while (q--) {
int a, b; cin >> a >> b;
cout << sktra(a, b) << "\n";
}
}
