#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll, ll>
#define fi first
#define sec second
const ll INF = 1e9;
const ll MAXN = 5e4;
ll K, N, M, O, u, v, w, a, b;
pii cur;
vector <ll> kiri, kanan, ans;
vector <vector<pii>> queries, adj;
void dnc(ll l, ll r) {
if (l >= r) return;
ll mid = (l + r) / 2;
for (int j = max(0, mid * K); j <= min(N - 1, (mid + 1) * K - 1); j++) {
kiri[j] = 0;
for (int k = j - 1; k >= max(0, l * K); --k) {
kiri[k] = INF;
for (auto [x, cost] : adj[k]) {
if (x <= j && x > k) kiri[k] = min(kiri[k], kiri[x] + cost);
}
}
kanan[j] = 0;
for (int k = j + 1; k <= min(N - 1, (r + 1) * K - 1); k++) {
kanan[k] = INF;
for (auto [x, cost] : adj[k]) {
if (x >= j && x < k) kanan[k] = min(kanan[k], kanan[x] + cost);
}
}
for (int k = j; k >= max(0, l * K); --k) {
cur = {j, -INF};
// cout << j << "\n";
// for (auto [x, y] : queries[k]) cout << x << " " << y << " HERE\n";
for (auto it = lower_bound(queries[k].begin(), queries[k].end(), cur); it != queries[k].end() && (*it).fi <= min(N, (r + 1) * K - 1); ++it) {
// cout << "ya\n";
// cout << kiri[k] << " " << kanan[(*it).fi] << "\n";
ans[(*it).sec] = min(ans[(*it).sec], kiri[k] + kanan[(*it).fi]);
}
}
}
dnc(l, mid - 1);
dnc(mid + 1, r);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> K >> N >> M >> O;
kiri.resize(N), kanan.resize(N);
ans.resize(O + 1);
queries = vector<vector<pii>> (N + 5);
adj = vector<vector<pii>> (N + 5);
for (int i = 1; i <= M; i++) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= O; i++) {
cin >> a >> b;
queries[a].push_back({b, i});
ans[i] = INF;
}
for (int i = 0; i < N; i++) {
if (!queries[i].empty()) sort(queries[i].begin(), queries[i].end());
}
dnc(0, (N + K) / K - 1);
for (int i = 1; i <= O; i++) cout << (ans[i] == INF ? -1 : ans[i]) << "\n";
}
