// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 50000 + 5;
int n, k, m, q;
vector<ii> G[2][N];
ll dist[2][6][N], ans[N];
vector<array<int, 3>> queries;
void dijkstra(int T, int layer, int L, int R) {
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> Q;
REP(j, k) FOR(i, L * k, min(n, (R + 1) * k) - 1)
dist[T][j][i] = INF;
FOR(i, layer * k, min(n, (layer + 1) * k) - 1) {
dist[T][i - layer * k][i] = 0;
Q.push({0, i - layer * k, i});
}
while(!Q.empty()) {
ll du = Q.top()[0]; int u = Q.top()[2], t = Q.top()[1];
Q.pop();
if (du != dist[T][t][u]) continue;
for(ii v : G[T][u]) if (L * k <= v.fi && v.fi < (R + 1) * k) {
if (minimize(dist[T][t][v.fi], du + v.se))
Q.push({dist[T][t][v.fi], t, v.fi});
}
}
}
void DnC(int L, int R, vector<array<int, 3>> &queries) {
if (L + 1 >= R) {
for(auto &x : queries) {
for(ii v : G[0][x[0]]) if (v.fi == x[1])
ans[x[2]] = v.se;
}
return;
}
int mid = (L + R) >> 1;
vector<array<int, 3>> left, right;
dijkstra(0, mid, L, R);
dijkstra(1, mid, L, R);
for(auto &x : queries) {
if (x[1] / k <= mid) left.pb(x);
else if (x[0] / k >= mid) right.pb(x);
else {
REP(i, k)
minimize(ans[x[2]], dist[1][i][x[0]] + dist[0][i][x[1]]);
}
}
DnC(L, mid, left);
DnC(mid, R, right);
}
void init(void) {
cin >> k >> n >> m >> q;
FOR(i, 1, m) {
int a, b, t;
cin >> a >> b >> t;
G[0][a].pb(mp(b, t));
G[1][b].pb(mp(a, t));
}
FOR(i, 1, q) {
int a, b;
cin >> a >> b;
queries.pb({a, b, i});
}
}
void process(void) {
FOR(i, 1, q) ans[i] = INF;
DnC(0, n / k, queries);
FOR(i, 1, q) cout << (ans[i] == INF ? -1 : ans[i]) << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
