#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
const int N = 50000;
const int inf = 1234567890;
const int C = 2000;
const int Q = 10000;
int dp[N], inQue[N];
int preCompute[C][N];
vector<array<int, 2>> adj[N];
array<int, 2> ques[Q];
int occ[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k, n, m, q;
cin >> k >> n >> m >> q;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
int t;
cin >> t;
adj[v].push_back({u, t});
}
for (int i = 0; i < n; i++) {
dp[i] = inf;
inQue[i] = -1;
occ[i] = 0;
}
vector<int> all;
for (int i = 0; i < q; i++) {
cin >> ques[i][0] >> ques[i][1];
all.push_back(ques[i][0]);
++occ[ques[i][0]];
}
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
sort(all.begin(), all.end(), [&](int i, int j) {
return occ[i] > occ[j];
});
vector<int> pts;
for (int i = 0; i < min((int) all.size(), C); i++) {
pts.push_back(all[i]);
inQue[all[i]] = i;
}
for (int i = 0; i < (int) pts.size(); i++) {
int u = pts[i];
int b0 = u / k;
for (int j = b0 * k; j < n; j++) {
preCompute[i][j] = inf;
}
preCompute[i][u] = 0;
for (int it = (b0 + 1) * k; it < n; it++) {
for (auto x : adj[it]) {
preCompute[i][it] = min(preCompute[i][it], preCompute[i][x[0]] + x[1]);
}
}
}
for (int it = 0; it < q; it++) {
int u = ques[it][0];
int v = ques[it][1];
int b0 = u / k;
int b1 = v / k;
if (b0 == b1) {
cout << -1 << '\n';
} else {
int id = inQue[u];
if (id == -1) {
dp[u] = 0;
for (int i = (b0 + 1) * k; i <= v; i++) {
for (auto x : adj[i]) {
dp[i] = min(dp[i], dp[x[0]] + x[1]);
}
}
if (dp[v] < inf) {
cout << dp[v] << '\n';
} else {
cout << -1 << '\n';
}
dp[u] = inf;
for (int i = (b0 + 1) * k; i <= v; i++) {
dp[i] = inf;
}
} else {
if (preCompute[id][v] < inf) {
cout << preCompute[id][v] << '\n';
} else {
cout << -1 << '\n';
}
}
}
}
return 0;
}
