#include <iostream>
#include <array>
#include <cassert>
#include <algorithm>
#include <string>
#include <bitset>
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
#include <bits/stdc++.h>
#define cerr if(false)cerr
#endif
using namespace std;
using ll = long long;
const int N = 5e4 + 66;
const int K = 5;
int k;
using mat = array<array<ll, K>, K>;
mat g[N];
const ll inf = 1e18 + 126;
mat compute(mat a, mat b) {
mat c; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) c[i][j] = inf;
for (int i = 0 ; i < k ; ++ i) for (int j = 0 ; j < k ; ++ j) for (int l = 0 ; l < k ; ++ l) {
c[i][j] = min(c[i][j], a[i][l] + b[l][j]);
}
return c;
}
const int LOG = 18;
mat sp[N][LOG];
mat compute(int l, int r) {
mat cur; for (int i = 0 ; i < K ; ++ i) for (int j = 0 ; j < K ; ++ j) cur[i][j] = inf;
bool st = false;
int len = r - l + 1;
cerr << l << " " << r << " sdf\n";
for (int i = 0 ; i < LOG ; ++ i) {
if (len >> i & 1) {
cerr << "[" << l << " " << l + (1 << i) - 1 << "]\n";
if (!st) cur = sp[l][i], st = true;
else cur = compute(cur, sp[l][i]);
l += 1 << i;
}
}
return cur;
}
mat mid;
int qa[N], qb[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> k >> n >> m >> q;
for (int b = 0 ; b < n ; ++ b) {
for (int i = 0 ; i < k ; ++ i) {
for (int j = 0 ; j < k ; ++ j) {
g[b][i][j] = inf;
}
}
}
while (m--) {
int a, b, c;
cin >> a >> b >> c;
int ba = a / k, bb = b / k;
assert(ba + 1 == bb);
int ia = a % k, ib = b % k;
g[ba][ia][ib] = c;
}
for (int i = 0 ; i < n ; ++ i) {
sp[i][0] = g[i];
}
for (int j = 1 ; j < LOG ; ++ j) {
for (int i = 0 ; i + (1 << j) - 1 < n ; ++ i) {
sp[i][j] = compute(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0 ; i < q ; ++ i) {
cin >> qa[i] >> qb[i];
int ba = qa[i] / k, bb = qb[i] / k;
int ia = qa[i] % k, ib = qb[i] % k;
cerr << qa[i] << " " << qb[i] << "|" << ba << " " << bb << "|" << ia << " " << ib << endl;
ll ans;
if (ba == bb) {
ans = inf;
} else if (ba == bb - 1) {
ans = g[ba][ia][ib];
} else {
ans = inf;
int l = ba + 1, r = bb - 2;
mid = compute(l, r);
for (int s = 0 ; s < k ; ++ s) {
for (int t = 0 ; t < k ; ++ t) {
cerr << mid[s][t] << " ";
ans = min(ans, (ba == bb - 2 && s == t ? 0 : mid[s][t]) + g[ba][ia][s] + g[bb - 1][t][ib]);
}
cerr << endl;
}
}
if (ans >= inf) ans = -1;
cout << ans << "\n";
}
}
