#include <bits/stdc++.h>
#define int long long
#define taskname "main"
#define debug(a, l, r) for (int _i = (l); _i <= (r); _i++) cout<<(a)[_i]<<' '; cout<<'\n';
using namespace std;
const int
maxN = 1e5,
maxK = 5,
oo = 1e18;
int blsz, n, m, q,
g[maxN + 5][maxK + 5][maxK + 5],
p[maxN + 5][maxK + 5][maxK + 5];
struct Query
{
int u, v, i;
void read(int _i)
{
cin >> u >> v;
i = _i;
}
}; vector <Query> list_q;
struct HasI
{
int x, i;
bool operator < (const HasI &other) const
{
return i < other.i;
}
void print()
{
cout << x << ' ' << i << '\n';
}
};
void set_g(int &save, int x)
{
save = min(save, x);
}
void init_g()
{
for (int i = 0; i <= maxN; i++)
for (int j = 0; j <= maxK; j++)
for (int k = 0; k <= maxK; k++)
g[i][j][k] = oo;
}
void init()
{
cin >> blsz >> n >> m >> q;
init_g();
for (int i = 1; i <= m; i++)
{
int u, v, c; cin >> u >> v >> c;
set_g(g[u / blsz][u % blsz][v % blsz], c);
}
for (int i = 1; i <= q; i++)
{
Query tmp_q;
tmp_q.read(i);
list_q.push_back(tmp_q);
}
}
vector <HasI> spe_case(vector <Query> &list_q)
{
vector <HasI> res;
for (Query u: list_q)
{
if (u.u == u.v)
res.push_back({0, u.i});
else res.push_back({-1, u.i});
}
return res;
}
void init_p(int l, int r)
{
int mid = (l + r) >> 1;
for (int i = l; i <= r; i++)
for (int j = 0; j < 5; j++)
for (int k = 0; k < 5; k++)
p[i][j][k] = oo;
for (int j = 0; j < 5; j++)
p[mid][j][j] = p[mid + 1][j][j] = 0;
}
void build_pr(int l, int r)
{
int mid = (l + r) >> 1;
for (int layer = mid + 2; layer <= r; layer++)
{
for (int ust = 0; ust < 5; ust++)
{
for (int usuf = 0; usuf < 5; usuf++)
{
for (int upre = 0; upre < 5; upre++)
{
int &memo = p[layer][ust][usuf];
memo = min(memo, p[layer - 1][ust][upre] + g[layer - 1][upre][usuf]);
}
}
}
}
}
void build_pl(int l, int r)
{
int mid = (l + r) >> 1;
for (int layer = mid - 1; layer >= l; layer--)
{
for (int uend = 0; uend < 5; uend++)
{
for (int upre = 0; upre < 5; upre++)
{
for (int usuf = 0; usuf < 5; usuf++)
{
int &memo = p[layer][upre][uend];
memo = min(memo, p[layer + 1][usuf][uend] + g[layer][upre][usuf]);
}
}
}
}
}
int f_uvres(Query u, int mid)
{
int uv_res = oo;
for (int upre = 0; upre < 5; upre++)
{
for (int usuf = 0; usuf < 5; usuf++)
{
int dist1 = p[u.u / blsz][u.u % blsz][upre],
dist2 = g[mid][upre][usuf],
dist3 = p[u.v / blsz][usuf][u.v % blsz];
uv_res = min(uv_res, dist1 + dist2 + dist3);
}
}
return uv_res;
}
void move_res(vector <HasI> &vfrom, vector <HasI> &vto)
{
for (HasI u: vfrom)
vto.push_back(u);
vfrom.clear();
}
vector <HasI> dnc(int l, int r, vector <Query> &list_q)
{
vector <HasI> res;
if (l == r)
return spe_case(list_q);
int mid = (l + r) >> 1;
init_p(l, r); build_pl(l, r); build_pr(l, r);
vector <Query> list_ql, list_qr;
for (Query u: list_q)
{
if (u.v / blsz < mid + 1)
list_ql.push_back(u);
else if (mid < u.u / blsz)
list_qr.push_back(u);
else res.push_back({f_uvres(u, mid), u.i});
}
vector <HasI>
resl = dnc(l, mid, list_ql),
resr = dnc(mid + 1, r, list_qr);
move_res(resl, res); move_res(resr, res);
for (int i = l; i <= r; i++)
memset(p[i], 0, sizeof(p[i]));
return res;
}
void solve()
{
vector <HasI> res = dnc(0, n / blsz, list_q);
sort(res.begin(), res.end());
for (HasI u: res)
{
if (u.x == oo)
cout << -1 << '\n';
else cout << u.x << '\n';
}
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
if (fopen(taskname".inp", "r"))
{
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
init(); solve();
}
// Xet truong hop di nguoc va di cung o nua
