#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 3;
const int O = 1e4 + 3;
const int K = 5 + 3;
const int INF = 1e9;
void check_min(int &a, int b){ a = a < b ? a : b; }
int k, n, m, o;
vector<array<int, 3>> adj[N], rev_adj[N];
int ans[O], lef[N], rig[N];
void dnc(int l, int r, const vector<array<int, 3>> &queries){
if(queries.empty()) return;
if(l == r){
for(auto [a, b, idx]: queries)
ans[idx] = -1;
return;
}
int mid = (l + r) >> 1;
vector<array<int, 3>> todo[2];
vector<array<int, 3>> curr;
for(auto [a, b, i]: queries){
if(a / k <= mid && mid <= b / k){
curr.push_back({a, b, i});
continue;
}
if(b / k < mid) todo[0].push_back({a, b, i});
else todo[1].push_back({a, b, i});
}
for(int i = 0; i < k; ++i){
for(int j = 0; j < k; ++j)
lef[mid * k + j] = (j == i) ? 0 : INF;
for(int j2 = mid - 1; j2 >= l; --j2){
for(int j = 0; j < k; ++j)
lef[j2 * k + j] = INF;
for(auto [from, to, t]: rev_adj[j2 + 1])
check_min(lef[to], lef[from] + t);
}
for(int j = 0; j < k; ++j)
rig[mid * k + j] = (j == i) ? 0 : INF;
for(int j2 = mid + 1; j2 <= r; ++j2){
for(int j = 0; j < k; ++j)
rig[j2 * k + j] = INF;
for(auto [from, to, t]: adj[j2 - 1])
check_min(rig[to], rig[from] + t);
}
for(auto [a, b, idx]: curr)
check_min(ans[idx], lef[a] + rig[b]);
}
dnc(l, mid - 1, todo[0]), dnc(mid + 1, r, todo[1]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> n >> m >> o;
for(int i = 0; i < m; ++i){
int a, b, t;
cin >> a >> b >> t;
adj[a / k].push_back({a, b, t});
rev_adj[b / k].push_back({b, a, t});
}
vector<array<int, 3>> queries;
for(int i = 0; i < o; ++i){
int a, b;
cin >> a >> b;
queries.push_back({a, b, i});
}
fill(ans, ans + o, INF);
dnc(0, n / k, queries);
for(int i = 0; i < o; ++i)
if(ans[i] == INF)
ans[i] = -1;
for(int i = 0; i < o; ++i)
cout << ans[i] << "\n";
}
