#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 5e4 + 5;
const int INF = 1e9;
const int sqrtn = 500;
int k, n, m, o;
int len;
vector<pll> adj[maxn];
struct node{
vector<vector<int>> dist;
void init(){
dist.resize(k);
for(int i = 0; i < k; i++){
dist[i].resize(k, INF);
dist[i][i] = 0;
}
}
node(){
dist = vector<vector<int>>(k, vector<int>(k, INF));
}
node(vector<vector<int>> _dist) : dist(_dist){}
} st[maxn * 4];
node add(int m, node a, node b){
vector<vector<int>> ndist(k, vector<int>(k, INF));
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++){
for(int pos = 0; pos < k; pos++){
for(auto [x, w] : adj[m * k + pos]){
ndist[i][j] = min(ndist[i][j], a.dist[i][pos] + b.dist[x - m * k - k][j] + w);
}
}
}
}
return node(ndist);
}
void build(int v = 1, int l = 0, int r = len){
if(l == r){
st[v].init();
return;
}
int m = (l + r) / 2;
build(v * 2, l, m);
build(v * 2 + 1, m + 1, r);
// cout<<"combine : "<<l<<" "<<m<<" "<<r<<"\n";
st[v] = add(m, st[v * 2], st[v * 2 + 1]);
}
node qry(int l, int r, int v = 1, int L = 0, int R = len){
if(l <= L && r >= R) return st[v];
int m = (L + R) / 2;
if(r <= m) return qry(l, r, v * 2, L, m);
else if(l > m) return qry(l, r, v * 2 + 1, m + 1, R);
else return add(m, qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
int main(void){
fastio;
cin>>k>>n>>m>>o;
len = n / k;
for(int i = 0; i < m; i++){
int a, b, c;
cin>>a>>b>>c;
adj[a].eb(b, c);
}
build();
for(int i = 0; i < o; i++){
int a, b;
cin>>a>>b;
node mat = qry(a / k, b / k);
cout<<(mat.dist[a % k][b % k] < INF ? mat.dist[a % k][b % k] : -1)<<"\n";
}
}
