#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)
using namespace std;
template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2>
void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}
template<class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}
template<class T>
void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
struct Matrix{
vector<vector<ll>> a;
int n, m;
Matrix(int _n = 0, int _m = 0, ll c = 0){
n = _n;
m = _m;
a.resize(n, vector<ll>(m, c));
}
Matrix operator * (const Matrix &p) const{
Matrix ans(n, p.m, oo);
for(int i = 0; i < n; i++){
for(int j = 0; j < p.m; j++){
for(int k = 0; k < p.n; k++){
minimize(ans.a[i][j], a[i][k] + p.a[k][j]);
}
}
}
return ans;
}
};
const int maxN = 5e4 + 10, LOG = 16;
int K, N, M, Q;
Matrix dist[maxN][LOG];
void solve(){
cin >> K >> N >> M >> Q;
for(int i = 0; i <= (N - 1) / K; i++){
dist[i][0] = Matrix(K, K, oo);
}
for(int i = 1; i <= M; i++){
int u, v, c; cin >> u >> v >> c;
dist[u / K][0].a[u % K][v % K] = c;
}
clock_t start = clock();
for(int j = 1; j < LOG; j++){
for(int i = 0; i + MASK(j) <= (N - 1) / K; i++){
dist[i][j] = dist[i][j - 1] * dist[i + MASK(j - 1)][j - 1];
}
}
while(Q--){
int u, v; cin >> u >> v;
if(u == v){
cout << 0 << '\n';
continue;
}
if(u / K >= v / K){
cout << -1 << '\n';
continue;
}
int delta = v / K - u / K;
Matrix cur(K, K, oo);
cur.a[u % K][u % K] = 0;
int pos = u / K;
for(int i = 0; i < LOG; i++) if(BIT(delta, i)){
cur = cur * dist[pos][i];
pos += MASK(i);
}
ll ans = cur.a[u % K][v % K];
if(ans >= oo) ans = -1;
cout << ans << '\n';
}
cerr << "Time elapsed: " << clock() - start << " ms\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("walk.inp","r",stdin);
// freopen("walk.out","w",stdout);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
