#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define rep(i,l,r) for(int i = (l); i < r; i++)
#define per(i,r,l) for(int i = (r); i >= l; i--)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define ss second
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 998244353, maxn = 5e4 + 5, maxk = 5, maxlg = 18, inf = 1e9 + 5;
struct Query{
pp a, b;
int id;
};
int grp[maxn][maxk][maxk], ans[maxn], val[maxn][maxk][maxk], k;
void slv(int lx, int rx, vector<Query> v){
if(lx >= rx || v.empty()){
for(auto c: v){
ans[c.id] = -1;
}
return;
}
// cout << lx << ' ' << rx << ": ";
// for(auto c: v) cout << c.id << ' '; cout << endl;
int mid = (lx + rx) >> 1;
rep(i,0,k){
rep(j,0,k){
if(i != j) val[mid][i][j] = inf;
else val[mid][i][j] = 0;
}
}
per(i,mid - 1, lx){
rep(f,0,k){
rep(e,0,k){
val[i][f][e] = inf;
rep(x,0,k){
val[i][f][e] = min(val[i][f][e], val[i + 1][x][e] + grp[i][f][x]);
}
}
}
}
rep(i,mid + 1, rx + 1){
rep(f,0,k){
rep(e,0,k){
val[i][f][e] = inf;
rep(x,0,k){
val[i][f][e] = min(val[i][f][e], val[i - 1][f][x] + grp[i-1][x][e]);
}
}
}
}
vector<Query> l, r;
for(auto c: v){
if(c.b.ff < mid){
l.pb(c);
}else if(c.a.ff > mid){
r.pb(c);
}else{
ans[c.id] = inf;
rep(i,0,k){
ans[c.id] = min(ans[c.id], val[c.a.ff][c.a.ss][i] + val[c.b.ff][i][c.b.ss]);
}
if(ans[c.id] == inf) ans[c.id] = -1;
}
}
slv(lx, mid - 1, l), slv(mid + 1, rx, r);
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
int n, m, q; cin >> k >> n >> m >> q;
rep(i,0,n){
rep(j,0,k){
rep(t,0,k){
grp[i][j][t] = inf;
}
}
}
rep(i,0,m){
int u, v, w; cin >> u >> v >> w;
grp[u/k][u%k][v%k] = w;
}
vector<Query> qs;
rep(i,0,q){
int u, v; cin >> u >> v;
Query qq;
qq.a = {u/k, u%k}, qq.b = {v/k, v%k};
qq.id = i;
qs.pb(qq);
}
// for(auto c: qs) cout << c.a.ff << ' ' << c.a.ss << ' ' << c.b.ff << ' ' << c.b.ss << '\n'; cout << endl;
slv(0, n/k, qs);
rep(i,0,q) cout << ans[i] << '\n';
return 0;
}
