#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> vii;
typedef long long ll;
int INF=1e9;
int main() {
int K, N, M, O;
cin>>K>>N>>M>>O;
if(M==0){
for(int i=0; i<O; i++){
int a, b;
cin>>a>>b;
if(a==b) cout<<0<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
while(N%K!=0) N++;
int T=N/K;
vector<vector<vvi>> tolls(log2(T-1)+1, vector<vvi>(T-1, vvi(K, vi(K, 1e9+1))));
for(int i=0; i<M; i++){
int a, b, t;
cin>>a>>b>>t;
tolls[0][a/K][a%K][b%K]=t;
}
for(int i=1; (1<<i) <= T-1; i++){
for(int j=0; j+(1<<i)<T; j++){
for(int k=0; k<K; k++){
for(int l=0; l<K; l++){
for(int m=0; m<K; m++){
tolls[i][j][k][l]=min(tolls[i-1][j][k][m]+tolls[i-1][j+(1<<(i-1))][m][l], tolls[i][j][k][l]);
}
}
}
}
}
for(int i=0; i<O; i++){
int a, b;
cin>>a>>b;
int c=a/K;
int d=b/K;
if(c==d){
cout<<-1<<"\n";
continue;
}
int q=0;
vector<int> dp(K, 1e9+1);
dp[a%K]=0;
int e=d-c;
while(e>0){
vector<int> dp2(K, 1e9+1);
if(e%2==0){
q++;
e/=2;
continue;
}
for(int j=0; j<K; j++){
for(int k=0; k<K; k++){
dp2[j]=min(dp2[j], dp[k]+tolls[q][c][k][j]);
}
}
c+=(1<<q);
q++;
e/=2;
dp=dp2;
}
if(dp[b%K]>1e9) cout<<-1<<"\n";
else cout<<dp[b%K]<<"\n";
}
return 0;
}
