#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define fi first
#define se second
#define left __left
#define right __right
#define prev __prev
#define next __next
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
const long long INF = (long long) 1e18 + 7;
struct Query {
int u, v;
};
#define MAX_NODE 50500
#define MAX_QUERY 10100
int K, numNode, numEdge, numQuery;
vector<int> layer[MAX_NODE + 2];
vector<pair<int, int>> adj[MAX_NODE + 2], revAdj[MAX_NODE + 2];
Query query[MAX_QUERY + 2];
ll ans[MAX_QUERY + 2], minDist[MAX_NODE + 2];
void dnc(int l, int r, const vector<int> &que) {
if (l == r) return;
int g = (l + r) >> 1;
vector<int> solveLeft, solveRight, solve;
for (int id : que) {
if (query[id].v / K <= g) solveLeft.push_back(id);
else if (query[id].u / K > g) solveRight.push_back(id);
else solve.push_back(id);
}
if (!solveLeft.empty()) dnc(l, g, solveLeft);
if (!solveRight.empty()) dnc(g + 1, r, solveRight);
if (solve.empty()) return;
for (int nodes : layer[g]) minDist[nodes] = INF;
for (int nodes : layer[g]) {
minDist[nodes] = 0;
FORD(i, g - 1, l) {
for (int u : layer[i]) {
minDist[u] = INF;
for (const pair<int, int> &e : adj[u]) {
int v = e.fi, w = e.se;
minimize(minDist[u], minDist[v] + w);
}
}
}
FOR(i, g + 1, r) {
for (int u : layer[i]) {
minDist[u] = INF;
for (const pair<int, int> &e : revAdj[u]) {
int v = e.fi, w = e.se;
minimize(minDist[u], minDist[v] + w);
}
}
}
for (int id : solve) {
int u = query[id].u, v = query[id].v;
minimize(ans[id], minDist[u] + minDist[v]);
}
minDist[nodes] = INF;
}
}
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
cin >> K >> numNode >> numEdge >> numQuery;
FOR(i, 1, numEdge) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(v, w));
revAdj[v].push_back(make_pair(u, w));
}
/// toi da K diem in each layer;
FOR(i, 0, numNode - 1) layer[i / K].push_back(i);
FOR(i, 1, numQuery) ans[i] = INF;
vector<int> queries;
FOR(i, 1, numQuery) {
cin >> query[i].u >> query[i].v;
if (query[i].u > query[i].v) continue;
if (query[i].u == query[i].v) {ans[i] = 0; continue;}
if (query[i].u / K != query[i].v / K) queries.push_back(i);
}
dnc(0, (numNode - 1) / K, queries);
FOR(i, 1, numQuery) cout << (ans[i] != INF ? ans[i] : -1) << "\n";
return 0;
}
