#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(v) begin(v), end(v)
#define pll pair<ll, ll>
#define fi first
#define se second
#define vll vector<ll>
#define mll map<ll, ll>
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const ll N = 1e5 + 6, inf = 1e18 + 7, mod = 1e9 + 7;
ll n, m, k, q, ans[N], a[N], b[N], dist[N];
pll qry[N];
vll v;
vector<pll> adj[N], adj2[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;
void dijkstra(ll s, ll l, ll r) {
for (int i = l*k; i < min(n, r*k + k); ++i) dist[i] = inf;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj[u]) {
if (l <= b[v] && b[v] <= r && d + w < dist[v]) {
dist[v] = d + w;
pq.push({d+w, v});
}
}
}
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue;
for (auto [v, w] : adj2[u]) {
if (l <= b[v] && b[v] <= r && d + w < dist[v]) {
dist[v] = d + w;
pq.push({d+w, v});
}
}
}
}
void dnc(ll l, ll r, vll v) {
//cout << "L R " << l << " " << r << endl;
if (v.empty()) return;
ll mid = (l+r) / 2;
//cout << "mid " << mid << endl;
for (int i = mid*k; i < min(n, mid*k + k); ++i) {
//cout << "i " << i << endl;
dijkstra(i, l, r);
// for (int j = l*k; j < min(n, r*k + k); ++j)
// cout << j << " " << (dist[j] == inf ? -1 : dist[j]) << endl; cout << endl;
for (auto j : v) {
auto [x, y] = qry[j];
if (b[x] <= mid && mid < b[y]) ans[j] = min(ans[j], dist[x] + dist[y]);
}
}
vll vl, vr;
for (auto i : v) {
//cout << l << " " << r << " " << i << " " << ans[i] << endl;
auto [x, y] = qry[i];
if (b[y] <= mid) vl.pb(i);
if (b[x] > mid) vr.pb(i);
}
dnc(l, mid, vl);
dnc(mid+1, r, vr);
}
void solve() {
cin >> k >> n >> m >> q;
for (int i = 0; i < n; ++i) b[i] = i / k;
for (int i = 1; i <= m; ++i) {
ll x, y, w;
cin >> x >> y >> w;
adj[x].pb({y, w});
adj2[y].pb({x, w});
}
for (int i = 1; i <= q; ++i) {
ans[i] = inf;
cin >> qry[i].fi >> qry[i].se;
if (b[qry[i].fi] == b[qry[i].se]) ans[i] = -1;
else v.pb(i);
}
dnc(0, n-1, v);
for (int i = 1; i <= q; ++i) cout << (ans[i] == inf ? -1 : ans[i]) << endl;
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(".INP", "r")) {
freopen(".INP", "r", stdin);
freopen(".OUT", "w", stdout);
}
ll tc = 1;
// cin >> tc;
while (tc--) {
solve();
}
return 0;
}
