P6573 [BalticOI 2017] Toll

As a qualified freight company, you need to deliver goods while spending as little money as possible.

This city has $n$ locations, and there are $m$ edges between these $n$ locations. The freight company has received $o$ orders, and they need to minimize the money spent along the route. For each road, there are three pieces of information: - $a, b$ mean the road connects from $a$ to $b$; - $t$ means how much money this road costs. For each order, $a$ and $b$ are given, meaning you need to transport goods from $a$ to $b$. For each order, find the minimum money needed; if it cannot be delivered, output $-1$. In particular, for a road with endpoints numbered $a, b$, it is guaranteed that: $$\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$$ ($k$ is a given constant).

The first line contains four integers $k, n, m, o$, representing a constant, the number of locations, the number of edges, and the number of orders. The locations are numbered from $0$ to $n - 1$. The next $m$ lines each contain three integers $a, b, t$, meaning that it costs $t$ to go from $a$ to $b$. It is guaranteed that $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$, and between any two locations there is at most $1$ edge. The next $o$ lines each contain two integers $a, b$, meaning you need to transport goods from $a$ to $b$.

For each order, output one integer per line representing the answer.

#### Constraints **This problem uses bundled testdata.** - Subtask 1 (7 pts): $k = 1$. - Subtask 2 (10 pts): For every order, $a = 0$. - Subtask 3 (8 pts): $o \le 100$. - Subtask 4 (31 pts): $o \le 3000$. - Subtask 5 (44 pts): No special constraints. For $100\%$ of the testdata, $1 \le n \le 50000$, $1 \le o \le 10000$, $1 \le k \le 5$, $0 \le a < b < n$, $1 \le t \le 10000$. #### Notes **Translated from [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T3 Toll.** Translator: @[一只书虫仔](https://www.luogu.com.cn/user/114914)。 **This problem enforces $O2$ optimization.** Translated by ChatGPT 5