#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
void ckmin(int& a, int b){
a = min(a, b);
}
const int MOD = 1e9+7;
const int mx = 50005;
int K, N, M, O;
vpi adj[mx];
vpi radj[mx];
pair<vi, vi> mid_dists[1<<17][5];
void genDists(int L, int R, int ind = 1){
if(L > R) return;
int M = (L+R)/2;
//cout << "L, M, R: " << L << ", " << M << ", " << R << "\n";
for(int rem = 0; rem < K; rem++){ //gen distances from M*K+rem
//cout << "rem: " << rem << "\n";
{
mid_dists[ind][rem].f = vi((M-L+1)*K, MOD);
vi& v = mid_dists[ind][rem].f;
priority_queue<pi, vector<pi>, greater<pi>> pq;
v[M*K+rem-L*K] = 0;
pq.push(mp(v[M*K+rem-L*K], M*K+rem));
while(sz(pq)){
int node = pq.top().s; pq.pop();
for(auto u: radj[node]){
if(u.f < L*K) continue;
if(v[u.f-L*K] <= v[node-L*K]+u.s){
continue;
}
v[u.f-L*K] = v[node-L*K]+u.s;
pq.push(mp(v[u.f-L*K], u.f));
}
}
}
{
mid_dists[ind][rem].s = vi((R-M+1)*K, MOD);
vi& v = mid_dists[ind][rem].s;
priority_queue<pi, vector<pi>, greater<pi>> pq;
v[M*K+rem-M*K] = 0;
pq.push(mp(v[M*K+rem-M*K], M*K+rem));
while(sz(pq)){
int node = pq.top().s; pq.pop();
for(auto u: adj[node]){
if(u.f >= (R+1)*K) continue;
if(v[u.f-M*K] <= v[node-M*K]+u.s){
continue;
}
v[u.f-M*K] = v[node-M*K]+u.s;
pq.push(mp(v[u.f-M*K], u.f));
}
}
}
// cout << "mid_dists[ind][rem].f:" << "\n";
// for(int i = 0; i < sz(mid_dists[ind][rem].f); i++){
// cout << i << " " << mid_dists[ind][rem].f[i] << "\n";
// }
// cout << "mid_dists[ind][rem].s:" << "\n";
// for(int i = 0; i < sz(mid_dists[ind][rem].s); i++){
// cout << i << " " << mid_dists[ind][rem].s[i] << "\n";
// }
}
genDists(L, M-1, 2*ind);
genDists(M+1, R, 2*ind+1);
}
int getDist(int a, int b, int L, int R, int ind = 1){
int M = (L+R)/2;
if(b/K < M){
return getDist(a, b, L, M-1, 2*ind);
}
else if(M < a/K){
return getDist(a, b, M+1, R, 2*ind+1);
}
int res = MOD;
for(int rem = 0; rem < K; rem++){
ckmin(res, mid_dists[ind][rem].f[a-L*K]+mid_dists[ind][rem].s[b-M*K]);
}
return res;
}
int main(){
cin >> K >> N >> M >> O;
for(int i = 1; i <= M; i++){
int a, b, t;
cin >> a >> b >> t;
adj[a].pb(mp(b, t));
radj[b].pb(mp(a, t));
}
genDists(0/K, (N-1)/K);
for(int i = 1; i <= O; i++){
int a, b;
cin >> a >> b;
int ans = getDist(a, b, 0/K, (N-1)/K);
if(ans >= MOD) ans = -1;
cout << ans << "\n";
}
}
