#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
int main() {
vii graph[50001], group_jump[50001];
int n, dist[50001], y, m, o;
scanf("%d %d %d %d", &y, &n, &m, &o);
const int lim = 100, k = y;
rep(i, 0, m) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
graph[u].emplace_back(v, w);
}
for (int group = 0; (group + lim + 1) * k <= n; group += lim) {
int start = group * k, stop = start + k, next_group = group + lim, next_start = next_group * k, next_stop = next_start + k;
rep(region, start, stop) {
fill(dist + start, dist + next_stop, INF);
dist[region] = 0;
rep(i, start, next_stop) {
if (INF <= dist[i]) continue;
trav(edge, graph[i]) {
int v, w;
tie(v, w) = edge;
dist[v] = min(dist[v], dist[i] + w);
}
}
rep(i, next_start, next_stop) group_jump[region].emplace_back(i, dist[i]);
}
}
rep(x, 0, o) {
int a, b;
scanf("%d %d", &a, &b);
fill(dist + a, dist + b + 1, INF);
dist[a] = 0;
rep(i, a, b) {
if (sz(group_jump[i]) && group_jump[i][0].first <= b) {
while (sz(group_jump[i])) {
trav(edge, group_jump[i]) {
int v, w;
tie(v, w) = edge;
dist[v] = min(dist[v], dist[i] + w);
}
++i;
}
i = group_jump[i - 1][0].first - 1;
}
if (INF <= dist[i]) continue;
trav(edge, graph[i]) {
int v, w;
tie(v, w) = edge;
dist[v] = min(dist[v], dist[i] + w);
}
}
printf("%d\n", dist[b] < INF ? dist[b] : -1);
}
return 0;
}
