#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e4 + 5;
const int MAX_K = 5;
int k, n, m, q;
// 最大级别数，数值/k相同的放在一个层级
int level;
// 第一个维度：起始点所在级别
// 第二个维度：起始级别节点编号（%k结果）
// 第三个维度：目标级别节点编号（%k结果）
// 第四个维度：目标点所在级别（第一个维度 + 2^ 第四个维度 - 1）
int dat[MAX_N][MAX_K][MAX_K][16];
void build() {
// 最多有n/k层
n = n / k;
level = log2(n);
// 初始化表格
// 计算每个长度是2^j的区间
for (int j = 1; j <= level; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
// 需要求的级别区间：[i, i + 2 ^ j - 1]
// 左侧区间：开始是i，长度是2^(j-1) [i, i + 2 ^ (j - 1) - 1]
// 右侧区间：开始是i + 2 ^ (j - 1)，长度是2^(j-1) [i + 2 ^ (j - 1), i + 2 ^ j - 1]
// 枚举左侧级别的每个节点编号
for (int u = 0; u < k; u++) {
// 枚举右侧级别的每个节点编号
for (int v = 0; v < k; v++) {
// 枚举中间级别的每个节点编号，作为中继点
for (int p = 0; p < k; p++) {
// 第i个级别的第u个节点，到第i + 2 ^ j - 1个级别的第p个节点
// 第i + 2 ^ j个级别的第p个节点，到第i + 2 ^ j - 1个级别的第v个节点
int tmp = dat[i][u][p][j - 1] + dat[i + (1 << (j - 1))][p][v][j - 1];
dat[i][u][v][j] = min(dat[i][u][v][j], tmp);
}
}
}
}
}
}
void query(int a, int b) {
// a所在层级
int alevel = a / k;
// b所在层级
int blevel = b / k;
// a所在层级节点编号
int ano = a % k;
// b所在层级节点编号
int bno = b % k;
// 计算两个层级的差距
int dif = blevel - alevel;
// 第一个维度：0表示前一轮结果，1表示当前轮结果
// 第二个维度：该层级的第no个点
int tmp[2][MAX_N];
memset(tmp, 0x3F, sizeof(tmp));
tmp[0][ano] = 0;
// 获取dif二进制上每一个1
for (int i = 0; (1 << i) <= dif; i++) {
// 如果第i位是1
if ((1 << i) & dif) {
// 计算第alevel级别的ano个点，到第alevel + 2^i 级别的每个节点
// 最短距离是多少
// 初始化当前轮次结果
memset(tmp[1], 0x3F, sizeof(tmp[1]));
// 计算到当前层级的第u个节点
for (int u = 0; u < k; u++) {
// 从前一轮次的第v个节点过来
for (int v = 0; v < k; v++) {
tmp[1][u] = min(tmp[1][u], tmp[0][v] + dat[alevel][v][u][i]);
}
}
// 更新tmp[0]为tmp[1]的结果
memcpy(tmp[0], tmp[1], sizeof(tmp[0]));
// alevel去往后面的层级
alevel += (1 << i);
}
}
// 如果仍然是最大值，那么就是-1
if (tmp[0][bno] == 0x3F3F3F3F) {
cout << -1 << endl;
}
else {
cout << tmp[0][bno] << endl;
}
}
int main() {
// 读取数据
cin >> k >> n >> m >> q;
// 初始化为一个很大的数值
memset(dat, 0x3F, sizeof(dat));
// 读取m条边信息
int a, b, c;
for (int i = 0; i < m; ++i) {
cin >> a >> b >> c;
// a所在层级
int alevel = a / k;
// b所在层级（一定是a+1）
// a所在层级节点编号
int ano = a % k;
// b所在层级节点编号
int bno = b % k;
// 最后一个维度是0，代表alevel到alevel+1
dat[alevel][ano][bno][0] = c;
}
// 初始化表格数据
build();
// 读取q次查询
for (int i = 0; i < q; ++i) {
cin >> a >> b;
query(a, b);
}
}
