#include <bits/stdc++.h>
#define fi first
#define se second
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define coutE(x) {cout << x << '\n'; return;}
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define bs binary_search
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
#define db long double
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
using namespace std;
void file(string s){
if (s.empty()) return;
freopen((s + ".inp").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template <class X, class Y>
bool minimize(X &x, Y y){
if (x > y) return x = y, 1;
return 0;
}
template <class X, class Y>
bool maximize(X &x, Y y){
if (x < y) return x = y, 1;
return 0;
}
const int N = 1e5 + 5;
const ll LINF = 1e18;
int n, k, m, q;
vii g[N][2];
ii quer[N];
ll dist[10][N], ans[N];
bool ok(int u, int L, int R){
return L <= u/k && u/k <= R;
}
void dijkstra(int s, ll* dist, int L, int R, bool t){
//0 tang
//1 giam
For(i, L * k, (R + 1) * k - 1)
dist[i] = LINF;
priority_queue<ii, vii, greater<ii>> q;
dist[s] = 0;
q.push({0, s});
while (!q.empty()){
auto [d, u] = q.top(); q.pop();
if (dist[u] < d) continue;
for (auto [v, w]: g[u][t]) if (ok(v, L, R)){
if (minimize(dist[v], dist[u] + w)){
q.push({dist[v], v});
}
}
}
}
void dnc(int L, int R, vi& idx){
if (L >= R) return;
int mid = (L + R) >> 1;
rep(i, k){
dijkstra(mid * k + i, dist[i], mid, R, 0);
dijkstra(mid * k + i, dist[i], L, mid, 1);
}
vi left, right;
for (int i: idx){
auto [u, v] = quer[i];
if (u/k <= mid && mid <= v/k){
rep(x, k){
minimize(ans[i], dist[x][u] + dist[x][v]);
}
}
if (v/k < mid) left.pb(i);
if (u/k > mid) right.pb(i);
}
if (!left.empty()) dnc(L, mid - 1, left);
if (!right.empty()) dnc(mid + 1, R, right);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
file("");
cin >> k >> n >> m >> q;
rep(i, m){
int u, v, w; cin >> u >> v >> w;
g[u][0].pb({v, w}); g[v][1].pb({u, w});
}
vi idx;
rep(i, q){
int u, v; cin >> u >> v;
ans[i] = LINF;
if (u/k <= v/k){
idx.pb(i);
quer[i] = {u, v};
}
}
dnc(0, (n - 1)/k, idx);
rep(i, q) cout << (ans[i] == LINF ? -1 : ans[i]) << '\n';
return 0;
}
