#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
const int INF = 1e9;
const int N = 50005;
const int LOG = 17;
using dt = pair<ii, int>;
int k, n, m, o, ret[N];
int f[5][N], g[5][N];
vector<ii> go[N], back[N];
vector<dt> querys;
void divide(int lx, int rx, vector<dt> &ask) {
if (ask.empty()) return;
int mx = (lx+rx)/2;
int st = lx*k, en = min(n, (rx+1)*k);
for(int t=0; t<k; ++t) {
for(int i=st; i<en; ++i) {
f[t][i] = g[t][i] = INF;
}
}
int l = mx*k, r = min(n, l+k);
for(int m=l; m<r; ++m) {
f[m-l][m] = g[m-l][m] = 0;
for(int i=m; i>st; --i) {
for(ii x : back[i]) {
f[m-l][x.fi] = min(f[m-l][x.fi], f[m-l][i] + x.se);
}
}
for(int i=m; i<en-1; ++i) {
for(ii x : go[i]) {
g[m-l][x.fi] = min(g[m-l][x.fi], g[m-l][i] + x.se);
}
}
}
vector<dt> _left, _right;
for(auto x : ask) {
if (x.fi.se/k < mx) _left.emplace_back(x);
else if (x.fi.fi/k > mx) _right.emplace_back(x);
else {
for(int m=l; m<r; ++m) {
ret[x.se] = min(ret[x.se], f[m-l][x.fi.fi] + g[m-l][x.fi.se]);
}
}
}
divide(lx, mx-1, _left);
divide(mx+1, rx, _right);
}
void solve() {
cin >> k >> n >> m >> o;
for(int i=1; i<=m; ++i) {
int u, v, t;
cin >> u >> v >> t;
go[u].emplace_back(v, t);
back[v].emplace_back(u, t);
}
for(int i=1; i<=o; ++i) {
int u, v;
cin >> u >> v;
querys.push_back({{u, v}, i});
}
memset(ret, 0x3f, sizeof(ret));
divide(0, (n-1)/k, querys);
for(int i=1; i<=o; ++i) {
if (ret[i] < INF) cout << ret[i] << "\n";
else cout << "-1\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("input.inp", "r")) {
freopen("input.inp", "r", stdin);
freopen("input.out", "w", stdout);
}
solve();
}
