#include<bits/stdc++.h>
#define ll long long
#define int ll
#define pii pair<int,int>
#define p3i pair<int,pii>
using namespace std;
const int inf = 1e15;
const int maxn = 5e4 + 2;
const int maxq = 1e4 + 2;
int k,n,m,q;
int ans[maxq];
int d[maxn][7][7];
vector<pii> a[maxn],b[maxn];
int cv(int tk, int lvl) {
return (lvl-1) * k + tk;
}
pii cv(int u) {
return make_pair(u % k, u / k + 1);
}
void query(int l, int r, vector<p3i> qr) {
if (qr.size()==0) return;
if (l==r) {
for (p3i val : qr) {
int id = val.first;
ans[id] = (val.second.first == val.second.second) ? 0 : -1;
}
return;
}
for (int i = 1; i <= n; i++) {
for (int u = 0; u < k; u++) {
for (int v = 0; v < k; v++) {
d[i][u][v] = inf;
}
}
}
int mid = l + r >> 1;
for (int i = 0; i < k; i++) d[mid][i][i] = 0;
for (int i = mid - 1; i >= l; i--) {
for (int u = 0; u < k; u++) {
int f = cv(u,i);
for(pii val : a[f]) {
int g,t; tie(g,t) = val;
int um = cv(g).first;
for (int v = 0; v < k; v++) {
int h = cv(v,mid);
if (cv(v,mid) >= n) continue;
if (d[i+1][um][v] < inf) {
d[i][u][v] = min(d[i][u][v], d[i+1][um][v] + t);
}
}
}
}
}
for (int i = mid + 1; i <= r; i++) {
for (int u = 0; u < k; u++) {
int f = cv(u,i);
if (f >= n) continue;
for(pii val : b[f]) {
int g,t; tie(g,t) = val;
int um = cv(g).first;
for (int v = 0; v < k; v++) {
int h = cv(v,mid);
if (d[i-1][v][um] < inf) {
d[i][v][u] = min(d[i][v][u], d[i-1][v][um] + t);
}
}
}
}
}
vector<p3i> qrl,qrr;
for (p3i val : qr) {
int l,r; tie(l,r) = val.second;
int u,lvlu; tie(u,lvlu) = cv(l);
int v,lvlv; tie(v,lvlv) = cv(r);
int id = val.first;
if (lvlv <= mid) qrl.push_back(val);
else if (lvlu >mid) qrr.push_back(val);
else {
ans[id] = inf;
for (int f = 0; f < k; f++) {
ans[id] = min(ans[id], d[lvlu][u][f] + d[lvlv][f][v]);
}
if (ans[id] >= inf) ans[id] = -1;
}
}
query(l,mid,qrl);
query(mid+1,r,qrr);
}
void solve() {
cin >> k >> n >> m >> q;
int lvl = n / k + (n%k != 0);
for (int i = 1; i <= m; i++) {
int x,y,t; cin >> x >> y >> t;
a[x].push_back({y,t});
b[y].push_back({x,t});
}
vector<p3i> qr;
for (int i = 1; i <= q; i++){
int x,y; cin >> x >> y;
qr.push_back({i,{x,y}});
}
query(1,lvl,qr);
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
}
void file(string name) {
if (fopen((name + ".inp").c_str(), "r")) {
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
signed main() {
file("toll");
cin.tie(0) -> sync_with_stdio(0);
solve();
return 0;
}
