题目描述
JOI 王国是一个由 $N$ 座城市组成的王国，这些城市从 $1$ 到 $N$ 编号。在 JOI 王国中，有 $M$ 条连接这些城市的单向高速公路，从 $1$ 到 $M$ 编号。经过高速公路 $i$（$1 \le i \le M$）可以从城市 $A_i$ 移动到城市 $B_i$，通行所需的时间为 $L_i$。
每次经过一条高速公路都会产生通行费。高速公路 $i$ 的通行费最便宜时为 $C_i$，但由于 JOI 王国的工人们都讨厌加班，离某个基准时刻 $0$ 越远，通行费就会越高。具体而言，如果在时刻 $t$ 从城市 $A_i$ 出发并经过高速公路 $i$，使用常数 $K$，通行费表示为 $C_i + K \times |t|$。其中 $|t|$ 表示 $t$ 的绝对值。
住在城市 $1$ 的你正在计划前往朋友居住的城市 $N$。你希望经过高速公路从城市 $1$ 移动到城市 $N$，因此首先想确认这是否可行；如果可行，还想求出通行费总和的最小值是多少。其中，移动路线以及从各座城市出发的时机都可以自由决定。特别地，可以在负时刻从城市 $1$ 出发，也可以在某座城市停留一段时间而不经过高速公路。
给定高速公路的信息以及常数 $K$，请编写程序，判断能否经过高速公路从城市 $1$ 移动到城市 $N$，并在可行的情况下求出通行费总和的最小值。
此外，在本题的限制条件下可以证明，如果能够经过高速公路从城市 $1$ 移动到城市 $N$，通行费总和的最小值一定为整数。
数据范围
- $2 \le N \le 4\,000$。
- $1 \le M \le 8\,000$。
- $0 \le K \le 100\,000$。
- $1 \le A_i \le N$（$1 \le i \le M$）。
- $1 \le B_i \le N$（$1 \le i \le M$）。
- $A_i \neq B_i$（$1 \le i \le M$）。
- $1 \le L_i \le 1\,000\,000$（$1 \le i \le M$）。
- $0 \le C_i \le 10^9$（$1 \le i \le M$）。
- 输入的所有值均为整数。
子任务
- （$9$ 分）$N \le 100$，$M \le 200$，$K = 0$。
- （$21$ 分）$N \le 100$，$M \le 200$，$L_i \le 20$（$1 \le i \le M$）。
- （$13$ 分）$N \le 100$，$M = N - 1$，$A_i = i$，$B_i = i + 1$（$1 \le i \le M$）。
- （$23$ 分）$N \le 100$，$M \le 200$，且满足以下限制：
- $N$ 为偶数，$\lfloor B_i / 2 \rfloor - \lfloor A_i / 2 \rfloor = 1$（$1 \le i \le M$）。这里，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
- （$16$ 分）$N \le 100$，$M \le 200$。
- （$11$ 分）$N \le 1\,500$，$M \le 3\,000$。
- （$7$ 分）无额外限制。
输入格式
输入按以下格式给出：
N M K A_1 B_1 L_1 C_1 A_2 B_2 L_2 C_2 : A_M B_M L_M C_M
输出格式
如果无法经过高速公路从城市 $1$ 移动到城市 $N$，则输出 -1。如果可行，则在 $1$ 行内输出表示通行费总和最小值的整数。
样例 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
15
将 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
4 4 0 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
9
与样例 $1$ 仅 $K$ 的值不同。
按如下方式移动时，通行费总和为 $9$：
- 时刻 $-3$：从城市 $1$ 出发前往城市 $2$。花费通行费 $2 + 0 \times |-3| = 2$。
- 时刻 $0$：到达城市 $2$，并立即前往城市 $3$。花费通行费 $4 + 0 \times |0| = 4$。
- 时刻 $1$：到达城市 $3$，并继续停留在城市 $3$。
- 时刻 $3$：从城市 $3$ 出发前往城市 $4$。花费通行费 $3 + 0 \times |3| = 3$。
- 时刻 $8$：到达城市 $4$。
由于不存在使通行费总和小于 $9$ 的移动方法，因此输出 $9$。
本样例输入满足子任务 $1, 2, 5, 6, 7$ 的限制。
样例 3
2 1 10 2 1 4 7
-1
由于无法经过高速公路从城市 $1$ 移动到城市 $2$，因此输出 -1。
本样例输入满足子任务 $2, 5, 6, 7$ 的限制。
样例 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
37
本样例输入满足子任务 $2, 3, 5, 6, 7$ 的限制。
样例 5
8 8 2 1 2 1 5 5 6 3 1 2 4 10 18 3 5 3 1 1 3 4 2 5 6 2 2 2 5 2 3 6 8 1 1
25
可能存在多条具有相同 $(A_i, B_i)$ 数对的道路。
本样例输入满足子任务 $2, 4, 5, 6, 7$ 的限制。
样例 6
6 10 100000 4 2 212037 752027141 2 5 667097 1571491 2 1 769275 576006950 1 2 711969 526189398 5 3 733555 206320177 3 4 364807 802102091 1 4 467240 183184247 3 5 44994 15991843 5 3 613192 782356546 4 6 832593 639529758
47546714005
本样例输入满足子任务 $5, 6, 7$ 的限制。