#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
/*const int MOD = (int) 1e9 + 7;
inline int lgput(int a, int b) {
int ans = 1;
while(b > 0) {
if(b & 1) ans = (1LL * ans * a) % MOD;
b >>= 1;
a = (1LL * a * a) % MOD;
}
return ans;
}
inline void mod(int &x) {
if(x >= MOD)
x -= MOD;
}
inline void add(int &x, int y) {
x += y;
mod(x);
}
inline void sub(int &x, int y) {
x += MOD - y;
mod(x);
}
inline void mul(int &x, int y) {
x = (1LL * x * y) % MOD;
}*/
/*int fact[], invfact[];
inline void prec(int n) {
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (1LL * fact[i - 1] * i) % MOD;
}
invfact[n] = lgput(fact[n], MOD - 2);
for(int i = n - 1; i >= 0; i--) {
invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
}
}
inline int comb(int n, int k) {
if(n < k) return 0;
return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/
using namespace std;
const int MAXN = 50000;
const int INF = 1e9;
vector < pair <int, int> > gl[MAXN + 1], gr[MAXN + 1];
vector < pair <int, int> > qry[MAXN + 1];
int a[MAXN + 1], b[MAXN + 1];
int dpl[MAXN + 1], dpr[MAXN + 1];
int sol[MAXN + 1], k;
void divide(int l, int r) {
if(l == r) {
return ;
}
int mid = (l + r) / 2;
for(int nod = max(mid - k, l); nod <= min(mid + k, r); nod++) {
dpr[nod] = 0;
for(int i = nod + 1; i <= r; i++) {
dpr[i] = INF;
for(auto it : gr[i]) {
if(it.first >= nod) {
dpr[i] = min(dpr[i], dpr[it.first] + it.second);
}
}
}
dpl[nod] = 0;
for(int i = nod - 1; i >= l; i--) {
dpl[i] = INF;
for(auto it : gl[i]) {
if(it.first <= nod) {
dpl[i] = min(dpl[i], dpl[it.first] + it.second);
}
}
}
for(int i = l; i <= nod; i++) {
int pos = (int) qry[i].size() - 1;
while(pos >= 0 && qry[i][pos].first >= nod) {
sol[qry[i][pos].second] = min(sol[qry[i][pos].second], dpl[i] + dpr[qry[i][pos].first]);
pos--;
}
}
}
for(int i = l; i <= mid; i++) {
while(qry[i].size() && qry[i].back().first > mid) {
qry[i].pop_back();
}
}
divide(l, mid);
divide(mid + 1, r);
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, n, m, o;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> k >> n >> m >> o;
for(i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
x++, y++;
gr[y].push_back({x, z});
gl[x].push_back({y, z});
}
for(i = 1; i <= o; i++) {
cin >> a[i] >> b[i];
a[i]++, b[i]++;
qry[a[i]].push_back({b[i], i});
sol[i] = INF;
}
for(i = 1; i <= n; i++) {
sort(qry[i].begin(), qry[i].end());
}
divide(1, n);
for(i = 1; i <= o; i++) {
if(sol[i] == INF) {
sol[i] = -1;
}
cout << sol[i] << "\n";
}
return 0;
}
