#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int N = 50010;
const int inf = 1000000000;
int dst[N][20][5],msk[N];
ll k,n,m,o;
void divi(int l,int r,int lvl,vector<vector<int>> &AL,vector<vector<int>> &nAL){
if(l == r) return;
int mid = (l+r)/2;
int medio = k*(mid+1)-1;
for(int i = 0; i <k;i++) dst[medio-i][lvl][k-1-i] =0;
for(int i = medio-k; i >= l*k;i--){
for(int j = 0; j <k;j++){
if(AL[i][j]){
for(int rr = 0; rr < k;rr++){
dst[i][lvl][rr] = min(dst[i][lvl][rr],dst[(i/k+1)*k+j][lvl][rr]+AL[i][j]);
if(dst[i][lvl][rr] > inf) dst[i][lvl][rr] = inf;
}
}
}
}
medio++;
for(int i = 0; i <k;i++) for(int j =0; j<k;j++){
if(medio + i < n){
if(nAL[medio+i][j]) dst[medio+i][lvl][j] = nAL[medio+i][j];
}
}
for(int i = medio+k; i <r*k+k &&i < n;i++){
for(int j = 0; j <k;j++){
if(nAL[i][j]){
for(int rr = 0; rr < k;rr++){
dst[i][lvl][rr] = min(dst[i][lvl][rr],dst[(i/k-1)*k+j][lvl][rr]+nAL[i][j]);
if(dst[i][lvl][rr] > inf) dst[i][lvl][rr] = inf;
}
}
}
}
for(int i = mid+1; i<=r;i++) msk[i]^=(1<<lvl);
divi(l,mid,lvl+1,AL,nAL);
divi(mid+1,r,lvl+1,AL,nAL);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> k >> n >> m >> o;
FOR(i,0,n) FOR(j,0,20) FOR(xx,0,5) dst[i][j][xx] = inf;
memset(msk,0,sizeof(msk));
vector<vector<int>> AL(n,vector<int>(k));
vector<vector<int>> nAL(n,vector<int>(k));
for(int i = 0; i< m;i++){
int a,b,toll; cin >> a >> b >> toll;
AL[a][b%k] = toll;
nAL[b][a%k] = toll;
}
divi(0,(n+k-1)/k-1,0,AL,nAL);
for(int i = 0; i < o; i++){
int a,b; cin >> a >> b;
if(a/k == b/k) cout <<"-1\n";
else{
int bits = __builtin_ctz(msk[a/k]^msk[b/k]);
int ans = 1e9;
for(int rr = 0; rr < k;rr++){
ans = min(ans,dst[a][bits][rr]+dst[b][bits][rr]);
}
if(ans == 1e9){
cout <<-1<<'\n';
}else cout << ans<<'\n';
}
}
}
