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$ 是一个给定的常数）。

第一行四个整数 $k,n,m,o$ 代表一个常数，地点的个数，边的个数，订单的个数。 点的编号为从 $0$ 到 $n - 1$。 接下来 $m$ 行每行三个整数 $a,b,t$ 代表从 $a$ 连向 $b$ 要花费 $t$，保证满足 $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$，并且两点之间连接的边数不超过 $1$ 条边。 接下来 $o$ 行每行两个整数 $a,b$ 代表要从 $a$ 运货到 $b$。

对于每个订单，输出一行一个整数表示答案。

#### 数据规模与约定 **本题采用捆绑测试。** - 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$ 优化。**