#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vvii = vector<vector<ii>>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
#define INF 1000000000
int K, N, M, O;
vvii rev;
vector<ii> queries;
vi sqrt_dcmp() {
int S = (int) sqrt(N);
int G = (int) ceil((double) N / S);
vvvi dist(G, vvi(S + K * 2, vi(S + K * 2, INF)));
for (int g = 0; g < G; ++g) {
for (int u = 0; u < S + K * 2; ++u) {
dist[g][u][u] = 0;
for (int v = u + 1; v < S + K * 2; ++v) {
if (u + g * S >= N || v + g * S >= N) continue;
for (ii e : rev[v + g * S]) {
int w = e.second - g * S;
if (w < u) continue;
dist[g][u][v] = min(dist[g][u][v], dist[g][u][w] + e.first);
}
}
}
}
vi answers;
for (ii q : queries) {
int a = q.first, b = q.second;
if (b < a) {
answers.push_back(-1);
continue;
}
int ans = INF;
int g1 = a / S, g2 = b / S;
if (g1 == g2) {
ans = dist[g1][a % S][b % S];
} else {
vvi d(G, vi(K * 2, INF));
for (int k = 0; k < K * 2; ++k) {
d[g1+1][k] = dist[g1][a % S][k + S];
}
for (int g = g1 + 2; g <= g2; ++g) {
for (int k1 = 0; k1 < K * 2; ++k1) {
for (int k2 = 0; k2 < K * 2; ++k2) {
d[g][k1] = min(d[g][k1], d[g-1][k2] + dist[g-1][k2][k1 + S]);
}
}
}
for (int k = 0; k < K * 2; ++k) {
ans = min(ans, d[g2][k] + dist[g2][k][b % S]);
}
}
answers.push_back(ans == INF ? -1 : ans);
}
return answers;
}
vi bruteforce() {
vi d0(N, INF);
d0[0] = 0;
for (int u = 1; u < N; ++u)
{
for (ii e : rev[u])
{
d0[u] = min(d0[u], d0[e.second] + e.first);
}
}
vi answers;
for (ii q : queries)
{
int a = q.first, b = q.second;
int ans;
if (a == 0) {
ans = d0[b];
}
else
{
vi d(N, INF);
d[a] = 0;
for (int u = a + 1; u < N; ++u)
{
for (ii e : rev[u])
{
d[u] = min(d[u], d[e.second] + e.first);
}
}
ans = d[b];
}
answers.push_back(ans == INF ? -1 : ans);
}
return answers;
}
int main() {
//freopen("out.txt", "w", stdout);
//freopen("in.txt", "r", stdin);
cin >> K >> N >> M >> O;
rev.resize(N);
queries.resize(O);
for (int i = 0; i < M; ++i) {
int a, b, t; cin >> a >> b >> t;
rev[b].emplace_back(t, a);
}
for (int i = 0; i < O; ++i) cin >> queries[i].first >> queries[i].second;
//vi expected = bruteforce();
vi actual = sqrt_dcmp();
//cout << "sqrt dcmp ok" << endl;
for (int i = 0; i < O; ++i) {
//if (expected[i] != actual[i]) {
// cout << queries[i].first << " " << queries[i].second << endl;
// cout << "Expected: " << expected[i] << ", Actual: " << actual[i] << endl;
//}
cout << actual[i] << endl;
}
return 0;
}
