/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int, int>
#define mp make_pair
#define endl '\n'
namespace custom_cp {
void setIO(const std::string &s = "", const std::string &in = ".in",
const std::string &out = ".out") {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
if (!s.empty()) {
freopen((s + in).c_str(), "r", stdin);
freopen((s + out).c_str(), "w", stdout);
}
}
} // namespace custom_cp
int dp[50000][17][5][5], ans[5][5], tmp[5][5];
void combine(int v[5][5], int x[5][5], int y[5][5], const int &k) {
for (int a = 0; a < k; a++) {
for (int b = 0; b < k; b++) {
for (int c = 0; c < k; c++) {
v[a][b] = std::min(v[a][b], x[a][c] + y[c][b]);
}
}
}
}
int main() {
custom_cp::setIO("");
int k, n, m, o;
std::cin >> k >> n >> m >> o;
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < m; i++) {
int u, v, t;
std::cin >> u >> v >> t;
dp[u / k][0][u % k][v % k] = t;
}
for (int j = 1; j < 17; j++) {
for (int i = 0; i + (1 << j) < (n - 1) / k + 1; i++) {
combine(dp[i][j], dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1], k);
}
}
for (int i = 0; i < o; i++) {
int u, v;
std::cin >> u >> v;
memset(ans, 0x3f, sizeof ans);
for (int i = 0; i < 5; i++)
ans[i][i] = 0;
for (int cur = u / k, end = v / k, b = 16; ~b; b--) {
if (cur + (1 << b) <= end) {
memset(tmp, 0x3f, sizeof tmp);
combine(tmp, ans, dp[cur][b], k);
memcpy(ans, tmp, sizeof ans);
cur += (1 << b);
}
}
std::cout << (ans[u % k][v % k] == 0x3f3f3f3f ? -1 : ans[u % k][v % k])
<< '\n';
}
}
