#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> a[50001];
int bin[50001][14][5];
int inf = 1e18;
int n, k, m, q;
vector<bool> vst(50001, false);
void dfs(int u){
vst[u] = true;
for (auto [v, w]:a[u]){
bin[u][0][v%k] = w;
if(!vst[v]){
dfs(v);
}
}
}
int query(int u, int v){
if(u/k >= v/k or !vst[u] or !vst[v])return -1;
int dif = v/k - u/k;
vector<int> sol(k, 0);
bool check = false;
int lev = u/k;
for (int bit = 13;bit>=0;--bit){
if(dif & (1<<bit)){
// cout << bit << '\n';
if(!check){
for (int p = 0;p<k;++p){
sol[p] = bin[u][bit][p];
}
check = true;
}else{
vector<int> tmp(k, inf);
for (int p = 0;p<k;++p){
for (int q = 0;q<k;++q){
if(bit==0){
// cout << p << ' ' << q << ' ' << sol[q] << '\n';
}
tmp[p] = min(tmp[p], sol[q] + bin[lev*k + q][bit][p]);
}
}
for (int p = 0;p<k;++p){
sol[p] = tmp[p];
}
}
// cout << '\n';
lev += (1<<bit);
}
}
return sol[v%k];
}
signed main(){
cin >> k >> n >> m >> q;
for (int i = 1;i<=m;++i){
int u, v, w;
cin >> u >> v >> w;
a[u].push_back({v, w});
}
// cout << vst[13];return 0;
for (int i = 0;i<n;++i){
vst[i] = false;
for (int j = 0;j<14;++j){
for (int p = 0;p<k;++p){
bin[i][j][p] = inf;
}
}
}
for (int i = 0;i<n;++i){
if(!vst[i] and !a[i].empty())dfs(i);
}
// cout << vst[13];return 0;
for(int j = 1;j<14;++j){
for (int i = 0;i<n;++i){
if(!vst[i])continue;
for (int p = 0;p<k;++p){
bin[i][j][p] = inf;
int lev = i/k;
for (int q = 0;q<k;++q){
/*if(i==0 and q==2 and p==2){
cout << (lev + (1<<(j-1)))*k+q << " LON\n";
cout << bin[i][j-1][q] << " BUOI\n";
cout << bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << " SV\n";
cout << bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << " NGU\n";
// return 0;
}*/
if(i==0 and j==1 and p==2){
// cout << i << ' ' << j << ' ' << p << ' ' << q << '\n';
// cout << bin[i][j-1][q] << ' ' << bin[ (lev + (1<<(j-1)))*k+q][j-1][p] << '\n';
}
bin[i][j][p] = min(bin[i][j][p], bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p]);
}
}
}
}
// cout << bin[2][1][0];return 0;
while(q--){
int u, v;
cin >> u >> v;
cout << query(u, v) << '\n';
}
}
