#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e4 + 5, SQRT = 3e2, INF = 1e9;
int k, n, m, q;
array<vector<pii>, MAX_N> adj;
unordered_map<int, int> dist;
unordered_set<int> seen;
priority_queue<pii, vector<pii>, greater<pii>> order;
void dijk(int s, bool halt = false) {
dist.clear(), seen.clear();
dist[s] = 0, order.push({0, s});
while (order.size()) {
int u = order.top().second;
order.pop();
if (halt && (u / k) % SQRT == 0) continue;
if (seen.count(u)) continue;
seen.insert(u);
for (pii x : adj[u]) {
int new_dist = dist[u] + x.second;
if (dist.count(x.first) && new_dist >= dist[x.first]) continue;
dist[x.first] = new_dist;
order.push({new_dist, x.first});
}
}
}
unordered_map<int, array<int, MAX_N>> sp;
void precomp() {
for (int u = 0; u < n; u++) {
if ((u / k) % SQRT != 0) continue;
dijk(u);
for (int v = 0; v < n; v++)
sp[u][v] = (dist.count(v)) ? dist[v] : INF;
}
}
int comp(int s, int f) {
dijk(s, true);
int ans = INF;
if (dist.count(f)) ans = min(ans, dist[f]);
for (pii x : dist)
if ((x.first / k) % SQRT == 0)
ans = min(ans, x.second + sp[x.first][f]);
return ans;
}
int main() {
// freopen("toll.in", "r", stdin);
cin >> k >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
}
precomp();
for (int i = 1; i <= q; i++) {
int s, f; cin >> s >> f;
int ans = comp(s, f);
cout << ((ans >= INF) ? -1 : ans) << '\n';
}
}
