#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma optimize("O2")
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define sp << " " <<
#define F(i, s, e) for(int i = s; i < e; i++)
#define R(i, s, e) for(int i = s; i >= e; i--)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define vb vector<bool>
#define endl '\n'
#define Tree tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
#define vpi vector<pii>
const int N = 5e4 + 5;
const int mod = 1e9 + 7;
const int inf = 1e15;
int dat[16][N][5][5], mask[N];
int k, n, m, q;
vvi go(N, vi(5, inf)), rgo(N, vi(5, inf));
void divi(int l, int r, int layer) {
if(l == r) return;
// calculate middle
int mid = (l + r) >> 1;
// calculate dat
// base cases
F(i, 0, k) {
dat[layer][mid][i][i] = 0;
}
F(i, mid+1, r+1) {
F(to, 0, k) {
F(from, 0, k) {
F(middle, 0, k) {
if(rgo[i*k+to][middle] < inf) dat[layer][i][from][to] = min(dat[layer][i][from][to], \
dat[layer][i-1][from][middle] + rgo[i*k+to][middle]);
}
}
}
}
R(i, mid-1, l) {
F(to, 0, k) {
F(from, 0, k) {
F(middle, 0, k) {
if(go[i*k+from][middle] < inf) dat[layer][i][from][to] = min(dat[layer][i][from][to], \
dat[layer][i+1][middle][to] + go[i*k+from][middle]);
}
}
}
}
// calculate mask
F(i, mid+1, r+1) {
mask[i] |= (1 << layer);
}
// branch into left and right segments
divi(l, mid, layer + 1);
divi(mid+1, r, layer + 1);
}
void solve() {
F(i, 0, 16) F(j, 0, N) F(k, 0, 5) F(l, 0, 5) dat[i][j][k][l] = inf;
cin >> k >> n >> m >> q;
F(i, 0, m) {
int u, v, w;
cin >> u >> v >> w;
if(u > v) swap(u, v);
go[u][v % k] = w;
rgo[v][u % k] = w;
}
int blockSize = (n + k - 1) / k;
divi(0, blockSize - 1, 0);
F(i, 0, q) {
int u, v;
cin >> u >> v;
int lu = u / k, lv = v / k;
if(u == v) cout << 0 << endl;
else if(lu >= lv) {
cout << -1 << endl;
} else {
int level = __builtin_ctz(mask[lu] ^ mask[lv]);
int mn = inf;
F(middle, 0, k) {
mn = min(mn, dat[level][lu][u % k][middle] + dat[level][lv][middle][v % k]);
}
if(mn < inf) cout << mn << endl;
else cout << -1 << endl;
}
}
}
int32_t main() {
cin.tie(0); ios_base::sync_with_stdio(0);
#ifdef Local
freopen("io.in", "r", stdin);
freopen("io.out", "w", stdout);
#endif
int t = 1;
//cin >> t;
while(t--) solve();
}
