P6573 [BalticOI 2017] Toll

作为一个合格的货运公司，在送达货物的同时也要让花的钱最少。

这座城市有 $n$ 个地点，这 $n$ 个地点之间有 $m$ 条边。 货运公司接到了 $o$ 个订单，他们要想方设法的让路途中花的钱最少。 对于每条路，都有三个信息： - $a,b$ 代表从 $a$ 连到 $b$； - $t$ 代表这条路需要多少钱。 并且对于每个订单，都给出 $a$ 和 $b$ 代表要把物品从 $a$ 运到 $b$ ，求每个订单需要花的最少的钱；如果无法送达就输出 $-1$。 特别的，对于两个编号为 $a,b$ 的路，一定满足： $$\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$$ （$k$ 是一个给定的常数）。

无

无

#### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（7 pts）：$k=1$。 - Subtask 2（10 pts）：每个订单中的 $a=0$。 - Subtask 3（8 pts）：$o \le 100$。 - Subtask 4（31 pts）：$o \le 3000$。 - Subtask 5（44 pts）：无特殊限制。 对于 $100\%$ 的数据，$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$。 #### 说明 **翻译自 [BOI 2017 D1](https://boi.cses.fi/files/boi2017_day1.pdf) T3 Toll。** 翻译者：@[一只书虫仔](https://www.luogu.com.cn/user/114914)。 **本题强制 $O2$ 优化。**