JOI 王国是一个由 $N$ 个城市组成的王国，这些城市编号从 $1$ 到 $N$。JOI 王国内有 $M$ 条连接这些城市的单向高速公路，每条高速公路编号从 $1$ 到 $M$。通过第 $i$ ($1 \leq i \leq M$) 条高速公路，可以从城市 $A_i$ 前往城市 $B_i$，通过所需时间为 $L_i$。

每次通过高速公路时都需要支付通行费用。第 $i$ 条高速公路的基本通行费为 $C_i$，但由于 JOI 王国的工人都讨厌加班，距离某一基准时刻 $0$ 越远（无论是正还是负），通行费就会越高。具体来说，如果在时刻 $t$ 从城市 $A_i$ 出发，经过第 $i$ 条高速公路，则通行费用为 $C_i + K\times |t|$。其中 $K$ 为给定常数，$|t|$ 表示 $t$ 的绝对值。

你居住在城市 $1$，计划前往朋友所在的城市 $N$。你想通过高速公路从城市 $1$ 前往城市 $N$。请首先判断是否可以实现；如果可以，请求出最小总通行费用。你可以自由选择行进路线以及每个城市的出发时机。特别地，你可以在负的时刻从城市 $1$ 出发，或在某个城市停留任意时间，而无需经过高速公路。

给定所有高速公路的信息以及常数 $K$，请判断能否通过高速公路从城市 $1$ 前往城市 $N$，并在可能时求出最小的总通行费用。

另外，在本题的约束条件下，如果可以从城市 $1$ 通过高速公路到达城市 $N$，则最小的总通行费用必定是整数，这一点可以得到证明。

输入按如下格式给出。

$N$ $M$ $K$
$A_1$ $B_1$ $L_1$ $C_1$
$A_2$ $B_2$ $L_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $L_M$ $C_M$

如果无法通过高速公路从城市 $1$ 到达城市 $N$，请输出 -1。
如果可以达到，请输出最小的总通行费用。

小子任务

1.（9 分） $N \leq 100$，$M \leq 200$，$K = 0$。
2.（21 分） $N \leq 100$，$M \leq 200$，$L_i \leq 20$ （$1 \leq i \leq M$）。
3.（13 分） $N \leq 100$，$M = N - 1$，$A_i = i$，$B_i = i+1$ （$1 \leq i \leq M$）。
4.（23 分） $N \leq 100$，$M \leq 200$，且满足以下约束：
- $N$ 为偶数，$\lfloor \frac{B_i}{2} \rfloor - \lfloor \frac{A_i}{2} \rfloor = 1$（$1 \leq i \leq M$）。其中 $\lfloor x \rfloor$ 为不超过 $x$ 的最大整数。
5.（16 分） $N \leq 100$，$M \leq 200$。
6.（11 分） $N \leq 1500$，$M \leq 3000$。
7.（7 分）无额外约束。

样例说明 1

JOI 王国的城与路情况如下图。圆圈表示城市，箭头表示道路，每条道路旁依次标注 $L_i$ 和 $C_i$。圆圈内的数字是城市编号。

如下移动总通行费用为 $15$：

• 时刻 $-1$：从城市 $1$ 出发前往城市 $3$。通行费用 $10+2\times |-1|=12$。
• 时刻 $0$：到达城市 $3$，立刻前往城市 $4$。通行费用 $3+2\times |0|=3$。
• 时刻 $5$：到达城市 $4$。

不存在能使总通行费用小于 $15$ 的其他方案，因此输出 $15$。

该输入满足小子任务 $2,5,6,7$ 的约束。

样例说明 2

与样例 $1$ 只差 $K$ 的值。

如下移动总通行费用为 $9$：

• 时刻 $-3$：从城市 $1$ 出发前往城市 $2$。通行费用 $2+0\times |-3|=2$。
• 时刻 $0$：到达城市 $2$，立刻前往城市 $3$。通行费用 $4+0\times |0|=4$。
• 时刻 $1$：到达城市 $3$，留在原地。
• 时刻 $3$：从城市 $3$ 出发前往城市 $4$。通行费用 $3+0\times |3|=3$。
• 时刻 $8$：到达城市 $4$。

不存在能使总通行费用小于 $9$ 的其他方案，因此输出 $9$。

此输入满足小子任务 $1,2,5,6,7$ 的约束。

样例说明 3

无法通过高速公路从城市 $1$ 到达城市 $2$，因此输出 -1。

该输入满足小子任务 $2,5,6,7$ 的约束。

样例说明 4

该输入满足小子任务 $2,3,5,6,7$ 的约束。

样例说明 5

存在多条连接相同 $(A_i,B_i)$ 对的道路。

该输入满足小子任务 $2,4,5,6,7$ 的约束。

样例说明 6

该输入满足小子任务 $5,6,7$ 的约束。

数据范围与约束

• $2 \leq N \leq 4000$。
• $1 \leq M \leq 8000$。
• $0 \leq K \leq 100\,000$。
• $1 \leq A_i \leq N$（$1 \leq i \leq M$）。
• $1 \leq B_i \leq N$（$1 \leq i \leq M$）。
• $A_i \neq B_i$（$1 \leq i \leq M$）。
• $1 \leq L_i \leq 1\,000\,000$（$1 \leq i \leq M$）。
• $0 \leq C_i \leq 10^9$（$1 \leq i \leq M$）。
• 输入的所有数均为整数。

由 ChatGPT 5 翻译