#include <algorithm>
#include <iostream>
using namespace std;
const int N_ = 1 << 16;
const int K = 5;
const int INF = 0x3f3f3f3f;
int **st[N_ << 1], n_;
int k;
int **new_dd(bool zeroes) {
int **dd = new int *[k];
for (int a = 0; a < k; a++) {
dd[a] = new int[k];
fill_n(dd[a], k, INF);
if (zeroes)
dd[a][a] = 0;
}
return dd;
}
void delete_dd(int **dd) {
for (int a = 0; a < k; a++)
delete[] dd[a];
delete[] dd;
}
int **merge(int **dd, int **ee) {
int **ff = new_dd(false);
for (int a = 0; a < k; a++)
for (int b = 0; b < k; b++)
for (int c = 0; c < k; c++)
ff[a][b] = min(ff[a][b], dd[a][c] + ee[c][b]);
return ff;
}
int **query(int l, int r) {
int **pp = new_dd(true), **qq = new_dd(true);
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if (l & 1) {
int **dd = merge(pp, st[l++]);
delete_dd(pp), pp = dd;
}
if (!(r & 1)) {
int **dd = merge(st[r--], qq);
delete_dd(qq), qq = dd;
}
}
int **dd = merge(pp, qq);
delete_dd(pp), delete_dd(qq);
return dd;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, m, q; cin >> k >> n >> m >> q;
n = (n - 1) / k;
for (n_ = 1; n_ < n; n_ <<= 1)
;
for (int i = 0; i < n_; i++)
st[i + n_] = new_dd(false);
while (m--) {
int i, j, w; cin >> i >> j >> w;
st[i / k + n_][i % k][j % k] = w;
}
for (int i = n_ - 1; i; i--) {
int l = i << 1, r = l ^ 1;
st[i] = merge(st[l], st[r]);
}
while (q--) {
int i, j; cin >> i >> j;
int l = i / k, a = i % k;
int r = j / k, b = j % k;
if (l == r) {
cout << "-1\n";
continue;
}
r--;
int **dd = query(l, r), d = dd[a][b];
if (d == INF)
d = -1;
cout << d << '\n';
delete_dd(dd);
}
return 0;
}
