#include <bits/stdc++.h>
using namespace std;
#define pb push_back
//#define int long long
const int maxN = 4e5 + 7;
vector<pair<int, int>> g[maxN];
int dp[maxN];
int pref[maxN];
int c[maxN];
void solve() {
int k, n, m, o;
cin >> k >> n >> m >> o;
for(int i = 0; i < n - 1; i++) {
c[i] = 1e9;
}
for(int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].pb({v, w});
c[u] = min(c[u], w);
}
for(int i = 0; i < n; i++) pref[i] = 1e9;
pref[0] = 0;
for(int i = 1; i < n; i++) {
if(c[i - 1] != 1e9 && pref[i - 1] != 1e9) {
pref[i] = pref[i - 1] + c[i - 1];
} else {
pref[i] = 1e9;
}
}
while(o--) {
int a, b;
cin >> a >> b;
if(k == 1) {
if(pref[a] == 1e9 || pref[b] == 1e9) {
cout << -1 << '\n';
} else {
cout << pref[b] - pref[a] << '\n';
}
continue;
}
for(int i = a; i <= b; i++) dp[i] = 1e9;
queue<int> q;
q.push(a);
dp[a] = 0;
while(!q.empty()) {
int v = q.front();
q.pop();
for(auto [u, w] : g[v]) {
if(dp[u] > dp[v] + w) {
dp[u] = dp[v] + w;
q.push(u);
}
}
}
if(dp[b] == 1e9) cout << -1 << '\n';
else cout << dp[b] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen("input.txt", "r", stdin);
int t = 1;
//cin >> t;
while(t--) solve();
}
