#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int K, N, M, O;
vector <vector <pair <int, int>>> adj;
struct node {
vector <vector <ll>> dis;
node () {
dis = vector <vector <ll>> (K, vector <ll> (K, 1e18));
}
};
struct stree {
#define lc v*2
#define rc v*2+1
vector <node> tree;
stree (int s) {
tree.resize(s * 4);
}
node combine(node a, node b, int l, int r) {
node c;
int tm = (l + r) / 2;
for (int l1 = 0; l1 < K; l1++) {
for (int l2 = 0; l2 < K; l2++) {
for (int i = K*tm; i < K*(tm+1); i++) {
for (auto tp : adj[i]) {
int j = tp.first, w = tp.second;
c.dis[l1][l2] = min(c.dis[l1][l2], a.dis[l1][i % K] + w + b.dis[j % K][l2]);
}
}
}
}
return c;
}
void pushup(int v, int l, int r) {
node a = tree[lc];
node b = tree[rc];
tree[v] = combine(a, b, l, r);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
for (int i = 0; i < K; i++)
tree[v].dis[i][i] = 0;
return;
}
int tm = (tl + tr) / 2;
build(lc, tl, tm);
build(rc, tm+1, tr);
pushup(v, tl, tr);
}
node query(int v, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r)
return tree[v];
int tm = (tl + tr) / 2;
if (r <= tm)
return query(lc, tl, tm, l, r);
if (l >= tm+1)
return query(rc, tm+1, tr, l, r);
node a = query(lc, tl, tm, l, r);
node b = query(rc, tm+1, tr, l, r);
return combine(a, b, tl, tr);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> K >> N >> M >> O;
adj.resize(N+1);
for (int i = 0; i < M; i++) {
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
}
stree tree((N-1)/K + 1);
tree.build(1, 0, (N-1)/K);
while (O--) {
int a, b;
cin >> a >> b;
node res = tree.query(1, 0, (N-1)/K, a/K, b/K);
ll ans = res.dis[a % K][b % K];
if (ans == 1e18)
ans = -1;
cout << ans << '\n';
}
}
