#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
typedef pair<int, int> pii;
const int N = (int)5e4 + 2;
const int inf = 1e9;
int res, k, lim, n, m, o, u, v, t;
int l[N << 2], h[N << 2];
struct TNode {
vector< vector<int> > dis;
TNode() {}
TNode(int k, int c): dis(k, vector<int>(k, c)) {}
void print() {
for(int i = 0; i < k; ++i) {
for(int j = 0; j < k; ++j) {
cout << (dis[i][j] == inf? -1: dis[i][j]) << ' ';
}
cout << '\n';
}
}
} st[N << 2], cost[N];
TNode ans;
bool minimize(int& a, int b) {
if(a <= b) return 0;
a = b; return 1;
}
TNode combine(const TNode& lef, const TNode& rig) {
if(lef.dis[0][0] == -1) return rig;
if(rig.dis[0][0] == -1) return lef;
TNode res = TNode(k, inf);
for(int i = 0; i < k; ++i) {
for(int j = 0; j < k; ++j) {
for(int l = 0; l < k; ++l) {
minimize(res.dis[i][j], lef.dis[i][l] + rig.dis[l][j]);
}
}
}
return res;
}
void build(int x, int low, int high) {
l[x] = low, h[x] = high, st[x] = TNode(k, inf);
if(l[x] == h[x]) {
st[x] = cost[low];
return;
}
int mid = (low + high) >> 1;
build(x << 1, low, mid);
build(x << 1 | 1, mid + 1, high);
st[x] = combine(st[x << 1], st[x << 1 | 1]);
}
TNode get(int x, int low, int high) {
if(l[x] > high || h[x] < low) return TNode(k, -1);
if(l[x] >= low && h[x] <= high) return st[x];
return combine(get(x << 1, low, high), get(x << 1 | 1, low, high));
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define FileName "test"
if(fopen(FileName".inp", "r")) {
freopen(FileName".inp", "r", stdin);
freopen(FileName".out", "w", stdout);
}
cin >> k >> n >> m >> o; lim = n / k + 1;
for(int i = 0; i <= lim; ++i) cost[i] = TNode(k, inf);
for(int i = 1; i <= m; ++i) {
cin >> u >> v >> t;
minimize(cost[u / k].dis[u % k][v % k], t);
}
build(1, 0, lim);
while(o --) {
cin >> u >> v;
if(u / k == v / k) {cout << "-1\n"; continue;}
ans = get(1, u / k, v / k - 1);
res = ans.dis[u % k][v % k];
if(res == inf) cout << "-1\n";
else cout << res << '\n';
}
}
