#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long
void solve() {
ll int k, n, m, o; cin >> k >> n >> m >> o;
const ll int LOG = 20;
// dp[i][i + 2 ^ k][x][y];
ll int dp[n / k][LOG][5][5];
memset(dp, 1, sizeof dp);
vector<vector<pair<ll int, ll int>>> adj(n);
for (ll int i = 0; i < m; i++) {
ll int a, b; cin >> a >> b;
ll int c; cin >> c;
adj[a].emplace_back(b, c);
}
for (ll int i = 0; i < n; i++) {
for (auto [v, wt] : adj[i]) {
dp[i / k][0][i % k][v % k] = wt;
}
}
auto combine = [&](ll int target[5][5], ll int a[5][5], ll int b[5][5]) {
for (ll int i = 0; i < k; i++) {
for (ll int j = 0; j < k; j++) {
for (ll int l = 0; l < k; l++) {
target[i][j] = min(target[i][j], a[i][l] + b[l][j]);
}
}
}
};
for (ll int i = 1; i < LOG; i++) {
for (ll int j = 0; (j + (1 << i)) < (n + k - 1) / k; j++) {
combine(dp[j][i], dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
}
}
// TODO: write query again
auto query = [&](ll int start, ll int end) {
ll int res[5][5];
memset(res, 1, sizeof res);
for (int i = 0; i < 5; i++) res[i][i] = 0;
ll int level = start / k;
ll int target = end / k;
int pow = LOG;
while (level != target) {
while (level + (1 << pow) > target) pow--;
// cout << pl(level) << pl(pow) << endl;
ll int new_res[5][5];
memset(new_res, 1, sizeof new_res);
combine(new_res, res, dp[level][pow]);
memcpy(res, new_res, sizeof res);
// for (int ii = 0; ii < k; ii++) {
// for (int jj = 0; jj < k; jj++) {
// cout << pl(ii) << pl(jj) << pl(res[ii][jj]) << endl;
// }
// }
level += (1 << pow);
}
return res[start % k][end % k];
};
while (o--) {
int a, b; cin >> a >> b;
ll int res = query(a, b);
if (res > 1e16) cout << -1 << endl;
else cout << res << endl;
}
// auto query = [&](ll int start, ll int levels, ll int en) {
// ll int res[5][5];
// ll int level = start / k;
// memset(res, 1, sizeof res);
// for (ll int i = 0; i < k; i++) res[i][i] = 0;
// ll int pow = LOG;
// while (levels > 0) {
// while (levels < (1 << pow)) pow--;
// ll int new_res[5][5];
// memset(new_res, 1, sizeof new_res);
// combine(new_res, res, dp[level][pow]);
// memcpy(res, new_res, sizeof res);
// level += (1 << pow);
// levels -= (1 << pow);
// }
// return res[start % k][en % k];
// };
// while (o--) {
// ll int a, b; cin >> a >> b;
// ll int levels = abs(a / k - b / k);
// if (levels == 0) {
// cout << -1 << endl;
// }
// ll int res = query(a, levels, b);
// if (res > 1e16) {
// cout << -1 << endl;
// } else {
// cout << res << endl;
// }
// }
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll int T = 1;
// cin >> T;
while (T--)
solve();
}
