#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) (a) = max((a), (b))
#define upmin(a, b) (a) = min((a), (b))
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using vvvpll = vector<vvpll>;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
ll k, n, m, q;
ll calc_times = 0;
//vvvpll min_dist; // min_dist[i][a][b] = min_dist from a to b (b is in the level which is 2^i above a)
map<pll, ll> dist;
inline ll get_parent_group(ll node, ll jump) {
if (node == -1) return -1;
ll group = node / k;
ll papa_group = group + ((ll)1 << jump);
return papa_group;
}
void calc(ll a, ll b) {
if (a == b) return;
if ((a / k) * k <= b && (a / k) * k + k - 1 >= b) {
dist[{a, b}] = INF;
}
ll cur_level = (a / k);
for (ll i = 16 - 1; i >= 0; i--) {
ll papa = get_parent_group(cur_level, i);
papa = cur_level + ((ll)1 << i);
if ((papa * k <= b)) { // && (papa * k + k - 1 >= b)
rep(nei, papa * k, papa * k + k) {
rep(node, cur_level * k, cur_level * k + k) {
if (dist.find({ a, nei }) == dist.end()) dist[{a, nei}] = INF;
if (dist.find({ a, node }) == dist.end()) dist[{a, node}] = INF;
if (dist.find({ node, nei }) == dist.end()) dist[{node, nei}] = INF;
dist[{a, nei}] = min(dist[{a, nei}], dist[{a, node}] + dist[{node, nei}]);
}
}
cur_level = papa;
}
}
}
void solve() {
cin >> k >> n >> m >> q;
//min_dist.clear(), min_dist.resize(16, vvpll(n, vpll(k + 1, { -1, INF })));
//dist.clear(), dist.resize(n, vll(n, INF));
calc_times = 0;
dist.clear();
rep(i, 0, m) {
ll a, b, t;
cin >> a >> b >> t;
if (dist.find({ a, b }) == dist.end()) dist[{a, b}] = INF;
dist[{a, b}] = min(dist[{a, b}], t);
}
rep(i, 0, n) dist[{i, i}] = 0;
rep(i, 1, 16) {
rep(node, 0, n) {
ll papa1 = get_parent_group(node, i - 1);
ll papa2 = get_parent_group(papa1 * k, i - 1);
if (papa2 == -1) continue;
rep(nei1, papa1 * k, papa1 * k + k) {
if (nei1 >= n) break;
rep(nei2, papa2 * k, papa2 * k + k) {
if (nei2 >= n) break;
if (dist.find({ node, nei1 }) == dist.end()) dist[{node, nei1}] = INF;
if (dist.find({ nei1, nei2 }) == dist.end()) dist[{nei1, nei2}] = INF;
if (dist.find({ node, nei2 }) == dist.end()) dist[{node, nei2}] = INF;
dist[{node, nei2}] = min(dist[{node, nei2}], dist[{node, nei1}] + dist[{nei1, nei2}]);
}
}
}
}
/*rep(i, 0, n) {
cout << "i = " << i << endl;
rep(j, 0, n) {
if (dist.find({ i, j }) == dist.end()) cout << -1 << ' ';
else cout << dist[{i, j}] << ' ';
}
cout << endl;
}*/
while (q--) {
ll a, b;
cin >> a >> b;
calc(a, b);
if (dist.find({a, b}) == dist.end()) {
dist[{a, b}] = INF;
}
if (dist[{a, b}] == INF) cout << -1 << '\n';
else cout << dist[{a, b}] << '\n';
}
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
2 7 7 1
0 2 1
0 3 1
1 3 1
3 4 2
2 4 3
3 5 3
5 6 1
0 6
3 14 12 1
0 3 2
1 4 1
2 5 3
4 6 5
4 8 4
3 6 3
6 10 1
7 11 1
8 11 1
11 13 2
10 13 2
10 12 1
4 13
*/
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll t = 1;
//cin >> t;
while (t--) {
solve();
}
}
