#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int MAX = 50000;
int k, n, m, q;
int A[MAX], B[MAX];
vector<int> blk[MAX];
int ans[MAX], ID[MAX];
int L[MAX][5], R[MAX][5];
vector<pair<int, int>> go[MAX], back[MAX];
bool minimize(int &x, const int &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
void divi(int l, int r, vector<int> &v) {
if (v.empty()) return;
if (l == r) {
for (int &id: v) {
if (A[id] == B[id]) ans[id] = 0;
else ans[id] = INF;
}
return;
}
int mid = l + r >> 1;
int lef = l * k, rig = min(n, r * k + k) - 1;
for (int i = lef; i <= rig; ++i) {
for (int t = 0; t < k; ++t) {
L[i][t] = R[i][t] = INF;
}
}
for (int i = 0; i < blk[mid].size(); ++i) {
int u = blk[mid][i]; L[u][i] = 0;
for (pair<int, int> &x: go[u]) {
int v = x.first, w = x.second;
R[v][i] = w;
}
}
for (int i = mid; i >= l + 1; --i) {
for (int &u: blk[i]) {
for (int t = 0; t < k; ++t) {
for (pair<int, int> &x: back[u]) {
int v = x.first, w = x.second;
minimize(L[v][t], L[u][t] + w);
}
}
}
}
for (int i = mid + 1; i <= r - 1; ++i) {
for (int &u: blk[i]) {
for (int t = 0; t < k; ++t) {
for (pair<int, int> &x: go[u]) {
int v = x.first, w = x.second;
minimize(R[v][t], R[u][t] + w);
}
}
}
}
vector<int> todo[2];
for (int &id: v) {
if (ID[A[id]] <= mid && mid < ID[B[id]]) {
for (int t = 0; t < k; ++t)
minimize(ans[id], L[A[id]][t] + R[B[id]][t]);
} else {
todo[ID[A[id]] > mid].push_back(id);
}
}
divi(l, mid, todo[0]); divi(mid + 1, r, todo[1]);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> k >> n >> m >> q;
while (m--) {
int a, b, t; cin >> a >> b >> t;
back[b].push_back({a, t});
go[a].push_back({b, t});
}
for (int i = 0; i < n; ++i) {
ID[i] = i / k;
blk[ID[i]].push_back(i);
}
vector<int> todo;
for (int i = 0; i < q; ++i) {
cin >> A[i] >> B[i];
todo.push_back(i);
}
memset(ans, 0x3f, sizeof ans);
divi(0, (n - 1) / k, todo);
for (int i = 0; i < q; ++i) {
if (ans[i] >= INF) cout << "-1\n";
else cout << ans[i] << '\n';
}
return 0;
}
