配点: 100 点
問題文
JOI王国是 N 是一个由城市组成的王国,这些城市有 它们的编号最大为 1 我决定将所有值添加到 N 。 JOI Kingdom拥有连接这些城市的网络。一方通行高速公路 M 书籍可用, 它们的编号最大为1 我决定将所有值添加到 M 。 高速公路 i (1 \leqq i \leqq M) 穿过城市 你可以移动到 A_i 来自城市 它的编号最大为 B_i ,经过的时间是 L_i 。
每次使用各高速公路时都会收取通行费。 高速公路 i 通行费最便宜。 C_i 然而,JOI王国的所有工人都不喜欢加班,所以有一定的标准时间 您距离 0 越远,收费就越高。 具体来说,城市 A_i 到时间 t 离开高速公路 经过 i 时,过路费不变 K 表示为 C_i + K\times |t| 。 然而,|t| 是 它仅由 t 的绝对值。
都市 1 您住在您朋友居住的城市。 N 。 你开车穿过高速公路到城市 我想去 1 来自城市 它的编号最大为 N ,所以首先我想看看是否可以,如果可以的话,我还想知道最低的总过路费是多少。 但您可以自由决定旅行路线以及从每个城市出发的时间。 尤其是城市 您可能会在负时间离开 1 ,或者您可能会在城市停留一段时间而不使用高速公路。
高速公路信息和常量 K 判断是否可以移动到 1 来自城市 它的编号最大为 N , 如果可能的话,编写一个程序来计算通行费的最小总和。
在这个问题的约束下,可以 如果可以行驶到 1 来自城市 它的编号最大为 N ,则可以证明路费的最小总和始终是整数。
制約
- 2 \leqq N \leqq 4\,000.
- 1 \leqq M \leqq 8\,000.
- 0 \leqq K \leqq 100\,000.
- 1 \leqq A_i \leqq N (1 \leqq i \leqq M).
- 1 \leqq B_i \leqq N (1 \leqq i \leqq M).
- A_i \neq B_i (1 \leqq i \leqq M).
- 1 \leqq L_i \leqq 1\,000\,000 (1 \leqq i \leqq M).
- 0 \leqq C_i \leqq 10^9 (1 \leqq i \leqq M).
- 所有输入值都是整数。
小課題
- (9 点) N \leqq 100,M \leqq 200,K = 0.
- (21 点) N \leqq 100,M \leqq 200,L_i \leqq 20 (1 \leqq i \leqq M).
- (13 点) N \leqq 100,M = N - 1,A_i = i,B_i = i+1 (1 \leqq i \leqq M).
- (23 点) N \leqq 100,M \leqq 200 并满足以下约束。
- N 是偶数,\lfloor \frac{B_i}{2} \rfloor - \lfloor \frac{A_i}{2} \rfloor = 1 (1 \leqq i \leqq M). 在这里,\lfloor x \rfloor 是 它仅由 x 代表以下最大的整数。
- (16 点) N \leqq 100,M \leqq 200.
- (11 点) N \leqq 1\,500,M \leqq 3\,000.
- (7 点)没有额外的限制。
入力
输入按以下格式给出。
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 行。
入力例 1
4 4 2 1 2 3 2 1 3 1 10 2 3 1 4 3 4 5 3
出力例 1
15
以下是JOI王国的城市和道路图。 圆圈代表城市,箭头代表道路,每条道路旁边都有该道路的名称。 L_i 和 C_i 的值按此顺序写入。 圆圈内写的数字代表该城市的编号。

如果您按以下方式移动,则总通行费将为 它变成 15 。
- 時刻 -1 : 都市 1 出发 前往 3 。通行费 10+2\times \left|-1\right|=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
出力例 2
9
入力例 1 是什么? 仅 K 的值不同。 到达
如果您按以下方式移动,则总通行费将为 它变成 9 。
- 時刻 -3 : 都市 1 出发 前往 2 。通行费 2+0\times \left|-3\right|=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
出力例 3
-1
市内直通高速公路
如果无法移动到 1 来自城市
它的编号最大为 2 ,-1 。
此输入示例是一个小作业。 2,5,6,7 满足约束。
入力例 4
4 3 5 1 2 3 1 2 3 1 10 3 4 7 6
出力例 4
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
出力例 5
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
出力例 6
47546714005
此输入示例是一个小作业。 5,6,7 满足约束。