题目描述

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$，则通行费可表示为 $C_i + K \times |t|$，其中 $|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$。若可以，则输出一行整数，表示通行费总和的最小值。

4 4 2
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

15

4 4 0
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

9

2 1 10
2 1 4 7

-1

4 3 5
1 2 3 1
2 3 1 10
3 4 7 6

37

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

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

提示

样例 1 解释

JOI 王国的城市与道路示意图如下所示。圆圈代表城市，箭头代表道路，每条道路旁标注了其对应的 $L_i$ 和 $C_i$ 的值（按此顺序）。圆圈内标注的数字代表该城市的编号。

:::align{center} :::

按以下方式移动时，通行费总和为 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$：从城市 3 出发，前往城市 4，通行费为 $3 + 0 \times |3| = 3$。
• 时刻 $8$：到达城市 4。

不存在通行费总和小于 9 的移动方案，因此输出 9。

该输入样例满足子任务 1、2、5、6、7 的约束。

样例 3 解释

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

该输入样例满足子任务 2、5、6、7 的约束。

样例 5 解释

可能存在多个具有相同 $(A_i, B_i)$ 对的道路。

该输入样例满足子任务 2、4、5、6、7 的约束。

数据范围

• $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 \ne 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$）。
• 所有输入的值均为整数。

子任务

1. （9 分）$N \le 100$，$M \le 200$，$K = 0$。
2. （21 分）$N \le 100$，$M \le 200$，$L_i \le 20$（$1 \le i \le M$）。
3. （13 分）$N \le 100$，$M = N - 1$，$A_i = i$，$B_i = i + 1$（$1 \le i \le M$）。
4. （23 分）$N \le 100$，$M \le 200$，并满足以下约束：
   • $N$ 为偶数，且对所有 $1 \le i \le M$，满足 $\lfloor B_i \div 2 \rfloor - \lfloor A_i \div 2 \rfloor = 1$。其中，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。
5. （16 分）$N \le 100$，$M \le 200$。
6. （11 分）$N \le 1\,500$，$M \le 3\,000$。
7. （7 分）无额外约束。

翻译由 Qwen3-235B 完成。