#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e9;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, n, m, q; cin>>k>>n>>m>>q;
vector<pii> g1[n + 1], g2[n + 1];
while (m--){
int x, y, t; cin>>x>>y>>t;
x++; y++;
g1[x].pb({y, t});
g2[y].pb({x, t});
}
vector<int> x(q + 1), y(q + 1), qs;
for (int i = 1; i <= q; i++){
cin>>x[i]>>y[i];
x[i]++; y[i]++;
if (x[i] >= y[i]) continue;
qs.pb(i);
}
vector<int> f(n + 1);
for (int i = 1; i <= n; i++){
f[i] = (i - 1) / k + 1;
}
vector<int> out(q + 1, inf);
vector<vector<int>> dist(k + 1, vector<int>(n + 1));
function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> qq){
if (l == r) return;
int m = (l + r) / 2;
vector<int> left, right, cur;
for (int i: qq){
if (f[y[i]] <= m){
left.pb(i);
continue;
}
if (f[x[i]] > m){
right.pb(i);
continue;
}
cur.pb(i);
}
for (int j = 1; j <= k; j++){
for (int i = (l - 1) * k + 1; i <= min(n, r * k); i++){
dist[j][i] = inf;
}
dist[j][(m - 1) * k + j] = 0;
for (int i = (m - 1) * k + j; i <= min(n, r * k ); i++){
for (auto [v, t]: g1[i]){
dist[j][v] = min(dist[j][v], dist[j][i] + t);
}
}
for (int i = (m - 1) * k + j; i >= (l - 1) * k + 1; i--){
for (auto [v, t]: g2[i]){
dist[j][v] = min(dist[j][v], dist[j][i] + t);
}
}
}
for (int i: cur){
for (int j = 1; j <= k; j++){
out[i] = min(out[i], dist[j][x[i]] + dist[j][y[i]]);
}
}
solve(l, m, left);
solve(m + 1, r, right);
};
solve(f[1], f[n], qs);
for (int i = 1; i <= q; i++){
cout<<((out[i] == inf) ? -1 : out[i])<<"\n";
}
}
