#include <bits/stdc++.h>
#define int int64_t
using namespace std;
vector<map<int, int, greater<int>>> graph; // map<target, distance>
int K;
const int INF = 1e10;
int findShortestDistance(int s, int e) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
unordered_map<int, int> distance;
pq.emplace(0, s);
while (!pq.empty()){
auto [cost, pos] = pq.top();
pq.pop();
if (distance.find(pos) != distance.end()) continue;
distance[pos] = cost;
int k = -1;
for (const auto& [p, c] : graph[pos]) {
if (p <= e) { // can't go backwards due to graph structure
if (k == -1) k = p / K;
if (k != p / K) break;
pq.emplace(cost + c, p);
}
}
}
return distance.find(e) == distance.end() ? INF : distance.at(e);
}
void addSkipEdges(int skipDistance) {
vector<tuple<int, int, int>> edgesToAdd;
for (int startCluster = 0; startCluster < graph.size() / K; startCluster+=skipDistance) {
for (int startNode = startCluster * K; startNode < (startCluster + 1) * K; startNode++) {
for (int endNode = (startCluster + skipDistance) * K; endNode < (startCluster + skipDistance + 1) * K; endNode++) {
if (endNode >= graph.size()) break;
edgesToAdd.emplace_back(startNode, endNode, findShortestDistance(startNode, endNode));
}
}
}
for (const auto& [startNode, endNode, distance] : edgesToAdd) {
graph[startNode][endNode] = distance;
}
}
main() {
int N,M,O;
cin >> K >> N >> M >> O;
graph.resize(N);
for (int i = 0; i < M; i++) {
int s, e, c;
cin >> s >> e >> c;
graph[s][e] = c;
}
for (int skipDist = 1; skipDist < N / K; skipDist *= 2) {
addSkipEdges(skipDist);
}
for (int o = 0; o < O; o++) {
int s, e;
cin >> s >> e;
int dist = findShortestDistance(s, e);
cout << (dist < INF ? dist : -1) << "\n";
}
}
