#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 = 2e18;
const ll MOD = 1e9 + 7;
ll k, n, m, q;
vvpll g;
//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) return;
for (ll i = 20 - 1; i >= 0; i--) {
ll papa = get_parent_group(a, i);
if ((papa * k <= b) && (papa * k + k - 1 >= b)) {
rep(nei, papa * k, papa * k + k) {
calc(nei, b);
if (dist.find({ a, b }) == dist.end()) dist[{a, b}] = INF;
if (dist.find({ a, nei }) == dist.end()) dist[{a, nei}] = INF;
if (dist.find({ nei, b }) == dist.end()) dist[{nei, b}] = INF;
dist[{a, b}] = min(dist[{a, b}], dist[{a, nei}] + dist[{nei, b}]);
//upmin(dist[{a, b}], dist[{a, nei}] + dist[{nei, b}]);
return;
}
}
}
}
void solve() {
cin >> k >> n >> m >> q;
g.clear(), g.resize(n);
//min_dist.clear(), min_dist.resize(20, vvpll(n, vpll(k + 1, { -1, INF })));
//dist.clear(), dist.resize(n, vll(n, INF));
rep(i, 0, m) {
ll a, b, t;
cin >> a >> b >> t;
g[a].push_back({ b, t });
//min_dist[0][a][(b % k)] = { 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, 20) {
rep(node, 0, n) {
rep(nei, 0, k) {
//min_dist[i][node][nei].first = min_dist[i - 1][node][nei].first;
//min_dist[i][node][nei].first = min_dist[i - 1][node][nei].first;
}
}
}*/
rep(i, 1, 20) {
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[i][j] == INF) 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 << endl;
else cout << dist[{a, b}] << endl;
}
}
/*
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
*/
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
ll t = 1;
//cin >> t;
while (t--) {
solve();
}
}
