#include <bits/stdc++.h>
#define int long long
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const int T=180;
const int INF=1e15;
typedef array<array<int,5>,5> mat;
void solve() {
int k,n,m,q;cin>>k>>n>>m>>q;
n/=T;n*=T;n+=T;
const array<int,5> BigChungus={INF,INF,INF,INF,INF};
const mat HugeChungus={BigChungus,BigChungus,BigChungus,BigChungus,BigChungus};
vector<mat> adj(n/k,HugeChungus);
L(i,0,m-1){
int a,b,w;cin>>a>>b>>w;
adj[a/k][a%k][b%k]=w;
}
auto merge=[&](mat a,mat& b)->mat{
mat aux=HugeChungus;
L(i,0,k-1){
L(j,0,k-1){
L(f,0,k-1){
aux[i][j]=min(aux[i][j],a[i][f]+b[f][j]);
}
}
}
return aux;
};
/*
for(int i=t-1;i<n;i+=t){
for(int j=0;j<t;j+=k){
int at=i-k+1-j*k;
if(j==0){
l(f,0,k-1)dp[at/k][f][f]=0;
}
else{
l(f,0,k-1)dp[at/k]=merge(adj[at/k],dp[at/k+1]);
}
}
}
*/
const int lg=16;
vector<vector<mat>> dp(lg,vector<mat>(n/k));
int lim=n/k;
L(i,0,lg-1){
L(j,0,lim-1){
if(i==0){
dp[i][j]=adj[j];
}
else{
if((1<<(i-1))+j<lim){
dp[i][j]=merge(dp[i-1][j],dp[i-1][j+(1<<(i-1))]);
}
}
}
}
while(q--){
int a,b;cin>>a>>b;
if(a>b)swap(a,b);
int na=a/k;
int nb=b/k;
int d=nb-na;
if(nb==na){
cout<<-1<<"\n";continue;
}
bool ok=0;
mat aux;
L(i,0,lg-1){
if(d&(1<<i)){
if(!ok){
aux=dp[i][na];
na+=(1<<i);
}
else{
ok=1;
aux=merge(aux,dp[i][na]);
na+=(1<<i);
}
}
}
cout<<(aux[a%k][b%k]<INF?aux[a%k][b%k]:-1)<<"\n";
}
}
int32_t main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin.exceptions(std::cin.failbit);
int T = 1;
// std::cin >> T;
while(T--) {
solve();
}
return 0;
}
