#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e13;
ll z[100005][5][5]; // Ma trận chuyển tiếp của từng block
vector<vector<ll>> f[400005]; // Cây phân đoạn: mỗi node lưu ma trận k x k
vector<vector<ll>> full; // Ma trận "vô cực" dùng khi truy vấn ngoài phạm vi
// Hàm combine: nhân ma trận chuyển tiếp với công thức:
// res[i][j] = min_{l=0}^{k-1} { left[i][l] + right[l][j] }
vector<vector<ll>> combine(vector<vector<ll>> left, vector<vector<ll>> right) {
vector<vector<ll>> res((int)left.size(), vector<ll>(left.size(), INF));
for (int i = 0; i < (int)left.size(); i++) {
for (int j = 0; j < (int)left.size(); j++) {
for (int l = 0; l < (int)left.size(); l++) {
res[i][j] = min(res[i][j], left[i][l] + right[l][j]);
}
}
}
return res;
}
// Xây dựng cây phân đoạn trên các block từ l đến r
void build(int id, int l, int r, int k) {
f[id].resize(k, vector<ll>(k, INF));
if (l == r) {
// Nạp ma trận của block l từ mảng z
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
f[id][i][j] = z[l][i][j];
}
}
return;
}
int mid = (l + r) / 2;
build(id * 2, l, mid, k);
build(id * 2 + 1, mid + 1, r, k);
f[id] = combine(f[id * 2], f[id * 2 + 1]);
}
// Hàm truy vấn trên cây phân đoạn: trả về ma trận chuyển tiếp tổng hợp cho block [x, y]
vector<vector<ll>> get(int id, int l, int r, int x, int y, int k) {
if (x > r || y < l) {
return full;
}
if (x <= l && r <= y) {
return f[id];
}
int mid = (l + r) / 2;
vector<vector<ll>> leftRes = get(id * 2, l, mid, x, y, k);
vector<vector<ll>> rightRes = get(id * 2 + 1, mid + 1, r, x, y, k);
if (leftRes == full) return rightRes;
if (rightRes == full) return leftRes;
return combine(leftRes, rightRes);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int k, a, b, c;
cin >> k >> a >> b >> c;
// Khởi tạo mảng z: gán giá trị INF cho mọi vị trí
for (int i = 0; i < 10005; i++){
for (int j = 0; j < k; j++){
for (int t = 0; t < k; t++){
z[i][j][t] = INF;
}
}
}
// Nhập các cạnh: với mỗi cạnh từ đỉnh x đến đỉnh y có trọng số t,
// ánh xạ vào block: x/k là chỉ số block, x%k là chỉ số trong block
for (int i = 1; i <= b; i++){
int x, y, t;
cin >> x >> y >> t;
z[x / k][x % k][y % k] = t;
}
// Tính số block: làm tròn lên, tức:
// n = ceil(a/k) = (a + k - 1) / k.
int n = (a + k - 1) / k;
// Khởi tạo ma trận full (vô cực) với kích thước k x k
full.resize(k, vector<ll>(k, INF));
// Xây dựng cây phân đoạn trên các block từ 0 đến n-1
build(1, 0, n - 1, k);
// Xử lý truy vấn
while(c--){
int x, y;
cin >> x >> y;
int sta = x / k;
int fin = y / k;
// Nếu nguồn và đích nằm trong cùng một block, theo quy định in -1
if (sta == fin) {
cout << -1 << "\n";
continue;
}
// Truy vấn trên các block từ sta đến fin-1
vector<vector<ll>> res = get(1, 0, n - 1, sta, fin - 1, k);
if (res == full || res[x % k][y % k] >= INF) {
cout << -1 << "\n";
} else {
cout << res[x % k][y % k] << "\n";
}
}
return 0;
}
