#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAXN = 50009, inf = 1e18;
vector <pair <int, int>> g[MAXN];
void solve() {
int k, n, m, q;
cin >> k >> n >> m >> q;
for(int i = 1; i <= m; i++) {
int a, b, t;
cin >> a >> b >> t;
g[a].emplace_back(b, t);
}
vector <int> dp(n);
while(q--) {
int a, b;
cin >> a >> b;
for(int i = a; i <= b; i++) {
dp[i] = inf;
}
dp[a] = 0;
for(int i = a; i <= b; i++) {
for(auto [to, w] : g[i]) {
dp[to] = min(dp[to], dp[i] + w);
}
}
cout<<(dp[b] == inf ? -1 : dp[b]) << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("7-router.in", "r", stdin);
//freopen("7-router.out.txt", "w", stdout);
int tt = 1;
//cin >> tt;
while (tt--){
solve();
}
}
