#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << '\n')
#define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
#define PAR2D(x) DEBUG(PRINT(#x << ":\n"); for (auto arr : x) {PAR(arr);} PRINT('\n'));
using i64 = long long;
constexpr int INF = 1000000007; //998244353;
int k, n, m, q;
vector<vector<pair<int, int>>> edges;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> k >> n >> m >> q;
edges.resize(n);
for (int i = 0; i < m; ++i) {
int a, b, w;
cin >> a >> b >> w;
edges[a].push_back({b, w});
}
vector<int> best(n, INF);
while (q--) {
int a, b;
cin >> a >> b;
fill(best.begin() + a, best.begin() + b + 1, INF);
best[a] = 0;
for (int i = a; i < b; ++i) {
for (auto [next, wt] : edges[i]) {
best[next] = min(best[next], best[i] + wt);
}
}
if (best[b] == INF) cout << -1 << '\n';
else cout << best[b] << '\n';
}
}
