#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
for (auto &i : a) {
is >> i;
}
return is;
}
struct BinaryJumps {
static const int lg = 16;
int k;
vector<vector<vector<int>>> up;
vector<vector<vector<ll>>> dp;
BinaryJumps(int _k, int n) : k(_k) {
up.resize(lg, vector<vector<int>>(k, vector<int>(n, -1)));
dp.resize(lg, vector<vector<ll>>(k, vector<ll>(n, infll)));
}
void add_edge(int u, int v, int w) {
if (dp[0][v % k][u] > w) {
up[0][v % k][u] = v;
dp[0][v % k][u] = w;
}
for (int i = 1; i < lg; ++i) {
for (int j = 0; j < k; ++j) {
for (int t = 0; t < k; ++t) {
if (up[i - 1][t][u] == -1) {
continue;
}
if (dp[i][j][u] > dp[i - 1][t][u] + dp[i - 1][j][up[i - 1][t][u]]) {
up[i][j][u] = up[i - 1][j][up[i - 1][t][u]];
dp[i][j][u] = dp[i - 1][t][u] + dp[i - 1][j][up[i - 1][t][u]];
}
}
}
}
}
ll dist(int u, int v) {
int d = v / k - u / k;
if (d < 0) {
return infll;
}
vector<ll> ans(k, infll);
ans[u % k] = 0;
int bl = u / k;
for (int i = lg - 1; i >= 0; --i) {
if (d >= (1 << i)) {
vector<ll> cur(k, infll);
for (int from = 0; from < k; ++from) {
for (int to = 0; to < k; ++to) {
cur[to] = min(cur[to], ans[from] + dp[i][to][bl * k + from]);
}
}
ans = cur;
bl += (1 << i);
d -= (1 << i);
}
}
return ans[v % k];
}
};
int32_t main() {
#ifdef LOCAL
freopen("/tmp/input.txt", "r", stdin);
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int k, n, m, q;
cin >> k >> n >> m >> q;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
}
BinaryJumps tr(k, n);
for (int i = n - 1; i >= 0; --i) {
for (auto [j, w] : g[i]) {
tr.add_edge(i, j, w);
}
}
while (q--) {
int u, v;
cin >> u >> v;
ll ans = tr.dist(u, v);
if (ans < infll) {
cout << ans << "\n";
} else {
cout << "-1\n";
}
}
return 0;
}
