#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int oo = 1e9;
struct conn{
int s;
int mc[5][5]; // from to
conn operator+(conn b){
conn ans;
ans.s = s;
rep(i,0,s) rep(j,0,s) ans.mc[i][j] = oo;
rep(i,0,s) rep(j,0,s) rep(k,0,s) ans.mc[i][j] = min(ans.mc[i][j], mc[i][k]+b.mc[k][j]);
return ans;
}
};
template<class T>
struct ST{
T unite(T l, T r){
return l+r; // or any associative operation
}
int n, mxd;
vector<vector<T>> suf, pref;
ST(vector<T> a) : n(sz(a)), mxd(__lg(n)+1), suf(mxd,vector<T>(n)), pref(mxd,vector<T>(n)){
for (int i=0,w=1; i<mxd; ++i, w*=2)
for (int b = 0; b < n; b += w){
int lim = min(b+w,n)-1;
T cur = a[b];
for(int k = b; k<lim; cur = unite(cur,a[++k]))
pref[i][k] = cur;
pref[i][lim] = cur;
cur = a[lim];
for (int k = lim; k>b; cur = unite(a[--k],cur))
suf[i][k] = cur;
suf[i][b] = cur;
}
}
// halfopen segment [l,r)
T get(int l, int r){
if (l==--r) return suf[0][l];
int d = __lg(l^r);
return unite(suf[d][l],pref[d][r]);
}
};
int main(){
cin.tie(NULL),cin.sync_with_stdio(false);
int k,n,m,o; cin >> k >> n >> m >> o;
int N = (n+k-1)/k;
vector<conn> conns(N);
rep(i,0,N){
conns[i].s = k;
rep(j,0,k) rep(l,0,k) conns[i].mc[j][l] = oo;
}
while (m--){
int a,b,t; cin >> a >> b >> t;
int bl = a/k;
conns[bl].mc[a%k][b%k] = min(conns[bl].mc[a%k][b%k], t);
}
ST st(conns);
while (o--){
int a,b; cin >> a >> b;
int ba = a/k, bb= b/k;
auto ret = st.get(ba,bb); // halfopen
int ans = ret.mc[a%k][b%k];
if (ans==oo) cout << "-1\n";
else cout << ans << '\n';
}
}
