#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, int>> a[50001];
int bin[50001][16][5];
int inf = 1e18;
int n, k, m, q;
vector<bool> vst(50001, false);
void dfs(int i){
stack<int> st;
st.push(i);
while(!st.empty()){
int u = st.top();
st.pop();
vst[u] = true;
for (auto [v, w]:a[u]){
if(!vst[v]){
st.push(v);
}
bin[u][0][v%k] = w;
}
}
}
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 = 15;bit>=0;--bit){
if(dif & (1<<bit)){
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){
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});
}
for (int i = 0;i<n;++i){
vst[i] = false;
for (int j = 0;j<16;++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);
}
for(int j = 1;j<16;++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((lev + (1<<(j-1)))*k+q>=n)continue;
bin[i][j][p] = min(bin[i][j][p], bin[i][j-1][q] + bin[ (lev + (1<<(j-1)))*k+q][j-1][p]);
}
}
}
}
while(q--){
int u, v;
cin >> u >> v;
int t = query(u, v);
if(t==inf)t = -1;
cout << t << '\n';
}
}
