#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#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;
inline long long key(long long a, long long b) {
return (a << 32) ^ b;
}
ll k, n, m, q;
//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)
unordered_map<ll, 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[key(a, b)] = INF;
return;
}
ll cur_level = (a / k);
for (ll i = 15 - 1; i >= 0; i--) {
ll papa = cur_level + ((ll)1 << i);
if (papa * k <= b) {
rep(nei, papa * k, papa * k + k) {
rep(node, cur_level * k, cur_level * k + k) {
if (!dist.count(key(a, nei))) dist[key(a, nei)] = INF;
if (!dist.count(key(a, node))) dist[key(a, node)] = INF;
if (!dist.count(key(node, nei))) dist[key(node, nei)] = INF;
dist[key(a, nei)] = min(dist[key(a, nei)], dist[key(a, node)] + dist[key(node, nei)]);
}
}
cur_level = papa;
}
}
}
void solve() {
cin >> k >> n >> m >> q;
//min_dist.clear(), min_dist.resize(15, vvpll(n, vpll(k + 1, { -1, INF })));
//dist.clear(), dist.resize(n, vll(n, INF));
dist.clear();
rep(i, 0, m) {
ll a, b, t;
cin >> a >> b >> t;
if (!dist.count(key(a, b))) dist[key(a, b)] = INF;
dist[key(a, b)] = min(dist[key(a, b)], t);
}
rep(i, 0, n) dist[key(i, i)] = 0;
rep(i, 1, 15) {
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.count(key(node, nei1))) dist[key(node, nei1)] = INF;
if (!dist.count(key(nei1, nei2))) dist[key(nei1, nei2)] = INF;
if (!dist.count(key(node, nei2))) dist[key(node, nei2)] = INF;
dist[key(node, nei2)] =min(dist[key(node, nei2)], dist[key(node, nei1)] + dist[key(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.count(key(a, b))) {
dist[key(a, b)] = INF;
}
if (dist[key(a, b)] == INF) cout << -1 << '\n';
else cout << dist[key(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();
}
}
