#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 5e4+5;
const int inf = 1e18;
int k, n, m, o;
vector<pair<int, int>> g[mx], rg[mx];
int dis[mx];
struct query {
int id;
int u, v;
};
int ans[mx];
void dij(int id, int l, int r) {
for (int i=l;i<=r;i++) {
dis[i] = inf;
}
dis[id] = 0;
priority_queue<pair<int, int>> pq;
pq.push({-dis[id], id});
while (pq.size()) {
auto [d, u] = pq.top(); pq.pop();
d = -d;
if (d > dis[u]) continue;
for (auto [v, w]:g[u]) {
if (v > r) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({-dis[v], v});
}
}
}
pq.push({-dis[id], id});
while (pq.size()) {
auto [d, u] = pq.top(); pq.pop();
d = -d;
if (d > dis[u]) continue;
for (auto [v, w]:rg[u]) {
if (v < l) continue;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({-dis[v], v});
}
}
}
}
void solve(int l, int r, vector<query> qs) {
if (l >= r) return;
int m = l + r >> 1;
vector<query> ls, rs, its;
for (auto [id, u, v]:qs) {
if (v/k < m) ls.push_back({id, u, v});
else if (m < u/k) rs.push_back({id, u, v});
else its.push_back({id, u, v});
}
solve(l, m-1, ls);
solve(m+1, r, rs);
for (int i=0;i<k;i++) {
dij(m*k+i, l*k, (r+1)*k-1);
for (auto [id, u, v]:its) {
ans[id] = min(ans[id], dis[u] + dis[v]);
}
}
}
signed main() {
cin >> k >> n >> m >> o;
for (int i=1;i<=m;i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
rg[v].push_back({u, w});
}
vector<query> qs;
for (int i=1;i<=o;i++) {
int u, v;
cin >> u >> v;
qs.push_back({i, u, v});
ans[i] = inf;
}
solve(0, n/k, qs);
for (int i=1;i<=o;i++) {
if (ans[i] == inf) cout << -1 << "\n";
else cout << ans[i] << "\n";
}
}
