#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vk vector
#define vl vector<ll>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ld long double
#define tt ll tcs; cin>>tcs; for(int i =0;i<tcs;i++)
# define FAST ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
vector<vector<ll>> mul(vector<vector<ll>> &a,vector<vector<ll>>&b,int p) {
vector<vector<ll>> c(p,vector<ll>(p,LLONG_MAX));
for(int i =0;i<p;i++) {
for(int j =0;j<p;j++) {
for(int k =0;k<p;k++) {
if (a[i][k]!=LLONG_MAX&&b[k][j]!=LLONG_MAX) {
c[i][j]=min(a[i][k]+b[k][j],c[i][j]);
}
}
}
}
return c;
}
void solve() {
int k,m,n,o;
cin>>k>>n>>m>>o;
int n_ = (n ) / k;
int len = ceil(log2(n_));
vector<vector<vector<vector<ll>>>> vm(n_,vector<vector<vector<ll>>>(len+1));
for (int i = 0 ; i < n_ ; i++) {
for (int j = 0 ; j <=len ; j++) {
vm[i][0] = vector<vector<ll>>(k,vector<ll>(k,LLONG_MAX));
}
}
for(int i =0;i<m;i++) {
int a,b,t;
cin>>a>>b>>t;
vm[a/k][0][a%k][b%k]=t;
}
for (int i = 0;i<n_;i++) {
for (int j = 1;j<=len;j++) {
if (i+(1<<(j-1))<n_) {
vm[i][j] = mul(vm[i][j-1],vm[i+(1<<(j-1))][j-1],k);
}
}
}
while (o--) {
int a,b;
cin>>a>>b;
int s = a/k;
int t = b/k;
int tim = t-s;
vector<vector<ll>> vv(k,vector<ll>(k,LLONG_MAX));
for(int i =0;i<k;i++) vv[i][i]=0;
while (tim!=0) {
int p = 31-__builtin_clz(tim);
vv = mul(vv,vm[s][p],k);
tim-=(1<<p);
s+=(1<<p);
}
if (vv[a%k][b%k]==LLONG_MAX) {
vv[a%k][b%k]=-1;
}
cout<<vv[a%k][b%k]<<endl;
}
}
int main() {
FAST {
solve();
}
}
