#include <bits/stdc++.h>
using namespace std;
#ifndef yoshi_likes_e4
#define endl '\n'
#endif
#define problem ""
#define multitest 0
#define debug(x) cerr << #x << " = " << x << endl;
template <typename T, typename Op> struct StaticRangeProduct
{
static const size_t B = 4;
std::vector<T> pref, suf, cur;
std::vector<std::vector<T>> spt;
Op op;
StaticRangeProduct(std::vector<T> p, Op opr) : op(opr)
{
cur = p;
const size_t SZ = (cur.size() + B - 1) / B * B;
cur.resize(SZ);
pref.resize(SZ);
suf.resize(SZ);
for (size_t i = 0; i < SZ; i++)
{
if (i % B == 0)
pref[i] = cur[i];
else
pref[i] = op(pref[i - 1], cur[i]);
}
for (size_t i = SZ - 1;; i--)
{
if (i % B == B - 1)
suf[i] = cur[i];
else
suf[i] = op(cur[i], suf[i + 1]);
if (i == 0)
break;
}
spt.assign(1, std::vector<T>(SZ / B));
for (size_t i = 0; i < SZ; i += B)
spt[0][i / B] = pref[i + B - 1];
for (size_t shift = 2; shift * B < SZ; shift *= 2)
{
spt.push_back(std::vector<T>(SZ / B));
bool flag = 0;
for (size_t k = 0; k * B < SZ; k += shift, flag ^= 1)
{
if (flag)
{
spt.back()[k] = spt[0][k];
for (size_t x = k + 1; x < std::min(SZ / B, k + shift); x++)
spt.back()[x] = op(spt.back()[x - 1], spt[0][x]);
}
else if (k + shift <= SZ / B)
{
spt.back()[k + shift - 1] = spt[0][k + shift - 1];
for (size_t x = k + shift - 2;; x--)
{
spt.back()[x] = op(spt[0][x], spt.back()[x + 1]);
if (x == k)
break;
}
}
}
}
}
T query(size_t l, size_t r)
{
T res;
if (l / B == r / B)
{
res = cur[l];
for (size_t i = l + 1; i <= r; i++)
res = op(res, cur[i]);
}
else
{
res = suf[l];
if (l / B + 1 <= r / B - 1)
{
if (l / B + 1 == r / B - 1)
res = op(res, spt[0][l / B + 1]);
else
{
size_t lg = __lg((r / B - 1) ^ (l / B + 1));
res = op(res, spt[lg][l / B + 1]);
res = op(res, spt[lg][r / B - 1]);
}
}
res = op(res, pref[r]);
}
return res;
}
};
struct Mat
{
int A[5][5];
Mat()
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
A[i][j] = 1e9;
}
};
auto weirdMatMul = [](Mat a, Mat b) {
Mat c;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
for (int k = 0; k < 5; k++)
c.A[i][k] = min(c.A[i][k], a.A[i][j] + b.A[j][k]);
return c;
};
void init()
{
}
void Yoshi()
{
int K, N, M, O;
cin >> K >> N >> M >> O;
vector<Mat> mats(N / K + 1);
while (M--)
{
int u, v, t;
cin >> u >> v >> t;
mats[u / K].A[u % K][v % K] = t;
}
StaticRangeProduct<Mat, decltype(weirdMatMul)> matq(mats, weirdMatMul);
while (O--)
{
int a, b;
cin >> a >> b;
if (a / K >= b / K)
cout << -1 << endl;
else
{
int d = matq.query(a / K, b / K - 1).A[a % K][b % K];
if (d > 5e8)
cout << -1 << endl;
else
cout << d << endl;
}
}
}
signed main()
{
#ifndef yoshi_likes_e4
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(problem ".inp", "r"))
{
freopen(problem ".inp", "r", stdin);
freopen(problem ".out", "w", stdout);
}
#endif
init();
int t = 1;
#if multitest
cin >> t;
#endif
while (t--)
Yoshi();
}
