#include <iostream>
#include <iomanip>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define _F ""
// #define MULTITEST
using namespace std;
#define MAXN 50000
#define MAXQ 10000
#define MAXVAL 1000000000
#define MAXK 5
struct adj_t {
int v, w;
};
struct query_t {
int u, v, ind;
};
// edge (u, v) -> b / k = 1 + a / k
int k, n, m, q;
vector<adj_t> adj[MAXN], radj[MAXN];
vector<query_t> queries;
int res[MAXQ];
void pre() {
cin >> k >> n >> m >> q;
int u, v, w;
while (m--) {
cin >> u >> v >> w;
adj[u].push_back({v, w});
radj[v].push_back({u, w});
}
queries.reserve(q);
query_t query;
for (int i = 0; i < q; i++) {
cin >> query.u >> query.v;
query.ind = i;
if (query.v / k <= query.u / k) res[query.ind] = -1;
else queries.emplace_back(query);
}
}
int f1[MAXK][MAXN], f2[MAXK][MAXN];
void dijkstra(int s, int blk, int brk, int* dist, vector<adj_t> adj[MAXN]) {
// k >= blk && k <= brk
for (int u = blk * k; u <= min(n - 1, (brk + 1) * k - 1); u++) dist[u] = MAXVAL;
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [distu, u] = pq.top(); pq.pop();
if (distu != dist[u]) continue;
for (auto [v, w]: adj[u]) {
if (v / k < blk || v / k > brk) continue;
if (distu + w < dist[v]) {
dist[v] = distu + w;
pq.push({dist[v], v});
}
}
}
}
void dnc(int l, int r, vector<query_t>& queries) {
if (l > r) return;
int mid = (l + r) >> 1;
for (int i = 0; i < k; i++) {
int u = mid * k + i;
if (u >= n) break;
dijkstra(u, l, r, f1[i], radj);
dijkstra(u, l, r, f2[i], adj);
}
vector<query_t> left, right;
for (query_t& query: queries) {
if (query.v / k < mid) left.push_back(query);
else if (query.u / k > mid) right.push_back(query);
else {
int resu = MAXVAL;
for (int i = 0; i < k; i++)
resu = min(resu, f1[i][query.u] + f2[i][query.v]);
res[query.ind] = resu == MAXVAL ? -1 : resu;
}
}
dnc(l, mid - 1, left);
dnc(mid + 1, r, right);
}
void run() {
dnc(0, (n - 1) / k, queries);
for (int i = 0; i < q; i++) cout << res[i] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(_F".inp", "r")) {
freopen(_F".inp", "r", stdin);
freopen(_F".out", "w", stdout);
}
pre();
int t = 1;
#ifdef MULTITEST
cin >> t;
#endif
while (t--) {
run();
}
}
/*
#++*
*-----::--+%
*---::---::--=------------=+## %%%#
+-:::::-===-------::::::::::::::=*+-:--::::-+%
+-::::-=:::::::::::::::::::::--=-::::==:::::::::-*
*# #=::---::::::::::::::::::::::::::::--:::------:::::=*
##** #=:--:::::::::::::::::::::::::::::::::--::::=-::-::::+
# +:--:::::::::::-::::::::::::::::::::::::--:::--:::-:::*
* *-+:::::::::::-:::::::::::::::--:::::::::::-:::--:::::::*
** #==::::::::::--::::::::::::::::::-:::::::::::-::--=:::-::=
* * *+::::::::::-:::::::::::::::::::::-:::::::::::--::-=:::-:-+
**# *-:::::::::-:::::::::::::::::::::-:::::::::::::--:::=:::-:-#
*=:::::::::-::::::::::::::::::::::::-::::::::::::-::---:::--*
*** +:::::::::-:::::::::::==:::::::::::::=::::::::::::-:--=::::-+
* *-::::::::--::::::::::-::--::::::::::::-:::::::::::---:--:::-=
+:::::::::=:::::-:::-::::::-:-::::::::-=::::::::::::--:-=-:::=
*-::::::::--:::-:::--::::::::=:-::::::::=-:::::::::::=-:-=-:::=
+:::::::::=::-:::--::::::::::::=-:::::::-=::::::::::::=:==--::=
*====+** #=:::::::::=-:--=--::-:::::::::::---::::::-::::::::::::=-==--::=
*-:::::::--:--:-::::::===-:-::::-::::::::::-:::-==-:::--:::::::::::+-==--::=
=-:----------:-::::::-::::::::::::::::::::::--:--:-===-:-:::::::::+==----:=
=-:----::--:-::::::-:::::::::::::::::::::::::::::::--:-:::::::::+:::::-==++*##
*-:--::----::::::-:::::::::::::::::::::::::::::::--:-:::::::::=--------:::::::-*
+-------=::::::-::=####*=::::::::::::::::::::::-::::::::::::-:----------::-=*
+==--*::::::=:::::::::::::::::::::=###*+-:::=:-:::::::-:=---------::--=
+-*=:::::-::::::::::::::::::::::::::=*-::-::::::::-+:=---:--::=+
*:*+-:::::=:::::::::::::::::::::::::::::=:::::::::+-==-::-=+=-=
*=++-::---=:::::::::::::::::::::::::::=:--:::::-+=-=-=+=====-=+
++*=*=::-===:::::::::::::::::::::::::---=-::::=++=+======------+
=+=+*-=+=-==:::::::::::::::::::::::-==*=-:::-+++=--------=+==+++*
#-*=*+----==++::::::::::-=:::::::::::-==-::=+*=------------=-----=+
*+==*=--------=+=-:::::--======++++--=====----=------------==----=+
+=-------------===+=--------------==-----------=------------=-----=*
*=------------==--------------------=-----------=====--------=-----=+
*=-------------==---------------------=----------=+====-------==+**++*
*=-------------==----------------------=---------=====--------==---==+
*=-------------==--------------------=++----------==----------=======+
#+=------------==------------------=+==-----------=----------==-=====+
+====-----------=----------------=+=====----------=---------=========*
+--:+*+---------+----------------*====-==---------+==------==+=+*+==*
*:-::++=-+==-----=+---------------===---==-----==+*#**=-=+==+++===+
+:-::++-::::-=====+=--------------------==-==++++++++::--::::-+++=+
#::-::++-::::::::::+#------------------=++++=--::-++=::-:::::::-+-=#
*::-::++-::::::::-++*+---------------=++--::::::=++=::-:::::::::-+-*
#-::-::++-:::::::-+++:-=------------=++--:::::::=++=::=:::::::::::==+
*:::--:++=::::::=++-::=+=---------=++--::::::::-+++::-::::::::::::==+
+:::-::=+=::::-+++-::---==-----=++**-:::::::::-+++::-:::::::::::::-==#
=::::-:-++-::-+++::--::::::----*:-++=:::::::::+++::--::::::::::::::=-*
#-::::=::++-:-++=::-:::::::::::::::=++-:::::::+++-::-:::::::::::::::+-+
*-::::-::=+==++-::-::::::::::::::-::++=::::::=++=::=::::::::::::::::==-*
*-:::::-:-++++=::-::::::::::::::::-::++=::::-++=::=:::::::::::::::::-=-+
::::::-+++=:::::::::::::::::::::::=++-:::=++-:::::::::::::::::::::--
*/
