#include <bits/stdc++.h>
using namespace std;
#define int long long int
int dp[500][500][5][5];
void solve() {
int n, o, m, k;
cin >> k >> n >> m >> o;
for (int i = 0; i < 55; i++) {
for (int j = 0; j < 55; j++) {
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
dp[i][j][x][y] = INT_MAX;
}
}
}
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dp[u/k][v/k][u%k][v%k] = min(dp[u/k][v/k][u%k][v%k], w);
}
for (int c = 0; c < n; c++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i/k][j/k][i%k][j%k] = min(dp[i/k][j/k][i%k][j%k], dp[i/k][c/k][i%k][c%k]+dp[c/k][j/k][c%k][j%k]);
}
}
}
while(o--) {
int a, b;
cin >> a >> b;
cout << dp[a/k][b/k][a%k][b%k] << endl;
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
t = 1;
while(t--) {
solve();
}
}
