#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << x << "]"
using namespace std;
bool M1;
const int mod = 1e9 + 7;
template<class X, class Y > bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
void add(int &a, const int &b){
a += b;
if (a >= mod) a -= mod;
}
void sub(int &a, const int &b){
a -= b;
if (a < 0) a += mod;
}
int mul(const int &a, const int &b){
return 1LL * a * 1LL * b % mod;
}
int bin_pow(int a, int k){
int res = 1;
while(k){
if (k & 1) res = mul(res, a);
a = mul(a, a); k >>= 1;
}
return res;
}
const int MAXN = 5e4 + 5, MAXQ = 1e4 + 4, MAXK = 6, infINT = 1e9 + 132112;
int numBlock, numNode, numEdge, numQuery, cost[MAXN][MAXK][MAXK];
struct Node{
int l, r;
long long dist[MAXK][MAXK];
Node(int v = 0, int _l = 0, int _r = 0): l(_l), r(_r) {
for(int i = 0; i < numBlock; i++)
for(int j = 0; j < numBlock; j++) dist[i][j] = v;
}
Node operator +(const Node &o){
Node res(infINT, l, o.r);
for(int i = 0; i < numBlock; i++)
for(int j = 0; j < numBlock; j++){
for(int a = 0; a < numBlock; a++)
for(int b = 0; b < numBlock; b++){
minimize(res.dist[i][j], dist[i][a] + cost[r][a][b] + o.dist[b][j]);
}
}
return res;
}
};
struct segmentTree{
int n;
vector<Node > node;
void build(int id, int l, int r){
if (l > r) return;
if (l == r){
node[id] = Node(infINT, l, r);
for(int i = 0; i < numBlock; i++) node[id].dist[i][i] = 0;
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
node[id] = node[id << 1] + node[id << 1 | 1];
}
segmentTree(int _n = 0): n(_n){
node.assign(n << 2 | 1, Node(infINT));
build(1, 0, n);
}
int cnt = 0;
Node get(int id, int l, int r, int u, int v){
if (l > r || l > v || r < u || u > v) return Node(-1);
if (l >= u && r <= v) return node[id];
int m = (l + r) >> 1;
Node left = get(id << 1, l, m, u, v);
Node right = get(id << 1 | 1, m + 1, r, u, v);
if (left.dist[0][0] == -1) return right;
if (right.dist[0][0] == -1) return left;
return left + right;
}
Node get(int u, int v){
return get(1, 0, n, u, v);
}
};
void input(){
cin >> numBlock >> numNode >> numEdge >> numQuery;
memset(cost, 0x3f, sizeof cost);
for(int i = 1; i <= numEdge; i++){
int u, v, w; cin >> u >> v >> w;
minimize(cost[u / numBlock][u % numBlock][v % numBlock], w);
}
}
void solve(){
segmentTree it(numNode / numBlock);
for(int q = 1; q <= numQuery; q++){
int u, v; cin >> u >> v;
Node ans = it.get(u / numBlock, v / numBlock);
long long res = ans.dist[u % numBlock][v % numBlock];
cout << (res < infINT ? res: -1) << '\n';
}
}
bool M2;
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
input();
solve();
cerr << (&M2 - &M1) / 1048576 << " mb\n";
cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}
