#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
using ll = long long;
int kk, n, m, q;
struct Matrix {
ll a[5][5];
inline ll *operator[](size_t x) {
return a[x];
}
inline const ll *operator[](size_t x) const {
return a[x];
}
} INF;
Matrix merge(const Matrix &a, const Matrix &b) {
Matrix c = INF;
for (int i = 0; i < kk; i++)
for (int j = 0; j < kk; j++)
for (int k = 0; k < kk; k++)
c[i][j] = min(c[i][j], a[i][k] + b[k][j]);
return c;
}
Matrix a[N];
struct TNode {
int l, r;
Matrix v;
} t[N << 2];
inline int lc(int pos) {
return pos << 1;
};
inline int rc(int pos) {
return pos << 1 | 1;
}
void build(int pos, int l, int r) {
t[pos].l = l;
t[pos].r = r;
if (l == r) {
t[pos].v = a[l];
return;
}
int mid = (l + r) >> 1;
build(lc(pos), l, mid);
build(rc(pos), mid + 1, r);
t[pos].v = merge(t[lc(pos)].v, t[rc(pos)].v);
}
Matrix query(int pos, int l, int r) {
if (t[pos].l == l && t[pos].r == r)
return t[pos].v;
int mid = (t[pos].l + t[pos].r) >> 1;
if (r <= mid)
return query(lc(pos), l, r);
else if (l > mid)
return query(rc(pos), l, r);
else
return merge(query(lc(pos), l, mid), query(rc(pos), mid + 1, r));
}
int main() {
ios::sync_with_stdio(false);
cin >> kk >> n >> m >> q;
for (int i = 0; i < kk; i++)
for (int j = 0; j < kk; j++)
INF[i][j] = LLONG_MAX >> 2;
for (int i = 0; i <= n / kk; i++)
a[i] = INF;
for (int i = 1; i <= m; i++) {
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
a[t2 / kk][t1 % kk][t2 % kk] = t3;
}
build(1, 0, n / kk);
while (q--) {
int t1, t2;
cin >> t1 >> t2;
if (t1 / kk >= t2 / kk) {
cout << -1 << endl;
continue;
}
ll ans = query(1, t1 / kk + 1, t2 / kk)[t1 % kk][t2 % kk];
if (ans == LLONG_MAX >> 2)
ans = -1;
cout << ans << endl;
}
return 0;
}
