#include <bits/stdc++.h>
template <class A, class B>
bool maximize (A &a, const B b){
if (a < b) {
a = b;
return true;
} return false;
}
template <class A, class B>
bool minimize (A &a, const B b) {
if (a > b) {
a = b;
return true;
} return false;
}
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define fi first
#define se second
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define ll long long
using namespace std;
int K, N, M, Q;
vector <pair <int, int>> G[50005], revG[50005];
void init(void) {
cin >> K >> N >> M >> Q;
FOR(i, 1, M) {
int u, v, w; cin >> u >> v >> w;
G[u].push_back({v, w});
revG[v].push_back({u, w});
}
}
namespace sub1 {
void solve() {
// Q * M * N * Log
while (Q--) {
int sour, fin;
cin >> sour >> fin;
vector <long long> dist(N + 2, 1e18);
priority_queue <array <long long, 2>, vector <array <long long, 2>>, greater <array <long long, 2>>> pq;
pq.push({dist[sour] = 0, sour});
while (!pq.empty()) {
int u = pq.top()[1];
long long cost = pq.top()[0];
pq.pop();
if (cost > dist[u]) continue;
for (auto it : G[u]) {
int v = it.fi, w = it.se;
if (minimize(dist[v], cost + w)) {
pq.push({dist[v], v});
}
}
}
cout << (dist[fin] >= 1e18 ? - 1 : dist[fin]) << "\n";
}
}
}
namespace sub2 {
long long ans[50005];
vector <array <int, 5>> query;
vector <int> node[50005];
long long dist[6][2][50005];
#define bg array <long long, 2>
priority_queue <bg, vector <bg>, greater <bg>> pq;
void dijk (int st, int id, int dir, int L, int R, vector <pair <int, int>> G[]) {
FOR(i, L, R) for (int &u : node[i]) {
dist[id][dir][u] = 1e18;
}
pq.push({dist[id][dir][st] = 0, st});
while (!pq.empty()) {
int u = pq.top()[1];
long long cost = pq.top()[0];
pq.pop();
if (cost > dist[id][dir][u]) continue;
for (auto it : G[u]) {
int v = it.fi, w = it.se;
if ((v / K) < L || (v / K) > R) continue;
if (minimize(dist[id][dir][v], cost + w)) {
pq.push({dist[id][dir][v], v});
}
}
}
}
void dnc(int L, int R, vector <array <int, 5>> &cur) {
if (L > R || cur.empty()) return;
if (L == R) return;
int mid = (L + R) >> 1;
vector <array <int, 5>> le, mi, ri;
for (auto x : cur) {
if (x[1] < mid) le.push_back(x);
else if (x[0] >= mid + 1) ri.push_back(x);
else mi.push_back(x);
}
FOR(i, 0, node[mid].size() - 1) {
dijk(node[mid][i], i, 0, L, R, revG);
dijk(node[mid][i], i, 1, L, R, G);
}
for (auto x : mi) {
FOR(i, 0, node[mid].size() - 1) {
minimize(ans[x[4]], dist[i][0][x[2]] + dist[i][1][x[3]]);
}
}
dnc(L, mid, le);
dnc(mid + 1, R, ri);
}
void solve() {
FOR(i, 0, N - 1) node[i / K].push_back(i);
FOR(i, 1, Q) ans[i] = 1e18;
FOR(i, 1, Q) {
int u, v; cin >> u >> v;
if (u == v) {
ans[i] = 0;
continue;
}
if (v / K <= u / K) continue;
query.push_back({u / K, v / K, u, v, i});
}
dnc(0, N / K, query);
FOR(i, 1, Q) {
if (ans[i] >= 1e18) cout << - 1 << "\n";
else cout << ans[i] << "\n";
}
}
}
void process(void) {
sub2::solve();
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define koa "boi17_toll"
if (fopen(koa".inp", "r")) {
freopen(koa".inp", "r", stdin);
freopen(koa".out", "w", stdout);
}
init();
process();
return 0;
}
