#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
const int MX = 50005;
const int INF = 1e9;
int lft[5][MX], rght[5][MX], k, n;
vector<pi>Q, f[MX], g[MX];
vi ans;
void div1(int le, int ri, vi v) {
if(v.empty()) return;
vi todo[2];
int m = (le+ri)/2, st = le*k, en = min((ri+1)*k, n);
for(int t=0; t<k; ++t) {
for(int j=0; j<en; ++j) lft[t][j] = rght[t][j] = INF;
}
int l = m*k, r = min(n, l+k);
for(int mx = l; mx < r; ++mx) {
lft[mx-l][mx] = rght[mx-l][mx] = 0;
for(int i=mx; i>st; --i) {
for(pi x: g[i]) lft[mx-l][x.first] = min(lft[mx-l][x.first], lft[mx-l][i] + x.second);
}
for(int i=mx; i<en-1; ++i) {
for(pi x: f[i]) rght[mx-l][x.first] = min(rght[mx-l][x.first], rght[mx-l][i] + x.second);
}
}
for(int t: v) {
int a = Q[t].first, b = Q[t].second;
if(a/k <= m && b/k > m) {
for(int mx = l; mx < r; ++mx) {
if(ans[t] == -1) ans[t] = lft[mx-l][a] + rght[mx-l][b];
else ans[t] = min(ans[t], lft[mx-l][a] + rght[mx-l][b]);
}
continue;
}
todo[(a/k)>m].push_back(t);
}
div1(le, m, todo[0]);
div1(m+1, ri, todo[1]);
}
void solve() {
int m, o;
cin >> k >> n >> m >> o;
while(m--) {
int a, b, w;
cin >> a >> b >> w;
f[a].push_back({b,w});
g[b].push_back({a,w});
}
vi v;
for(int i=0; i<o; ++i) {
v.push_back(i);
int a, b;
cin >> a >> b;
Q.push_back({a,b});
}
ans.assign(o, -1);
div1(0, (n-1)/k, v);
for(int x: ans) {
if(x >= INF) cout << -1 << endl;
else cout << x << endl;
}
}
int main( ){
//freopen("input1.txt", "r", stdin)
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--) solve();
}
