配点: 100 点
位于 IOI 镇 有 N 交叉路口, 它们的编号最大为1 从 N 。另外,M 有一条书路, 它们的编号最大为1 从 M 。每条路径都是 它连接 2 两个方向的不同交叉路口。路 i (1 \leqq i \leqq M) 是一个交集 A_i 和交叉路口 B_i 已连接。2 书中的不同道路从未连接同一组交叉路口。在这些道路上 1 以上 M 道路涂有由以下整数表示的颜色。 i 的当前颜色是 C_i 。多条道路可以涂成相同的颜色。
JOI 开发了一种机器人,可以在 IOI 镇的十字路口移动。当你告诉这个机器人道路的颜色时,机器人就会沿着指定颜色的路径移动到相邻的路口。但与机器人当前所在路口相连的道路中,指定颜色的道路为 2 如果有多个,它将停止而无法确定下一条路径。
您的目标是 1 向十字路口的机器人发出几条指令。 就是将其移动到 N 。然而,这对于当前的道路颜色来说不一定可行,因此需要改变一些道路的颜色。提前通过重新喷漆, 交叉路口机器人 我希望能够将其移至 N 。路 i (1 \leqq i \leqq M) 是 P_i 乘以日元,1 以上 M 您可以将其重新绘制为下面您最喜欢的整数颜色。
给定有关十字路口和道路的信息,编写一个程序来查找所需的最低金额。然而,无论你如何改变道路的颜色,机器人都无法穿过路口。
如果您无法将其移至 N ,请改为
输出 -1 。
入力
输入是按以下格式从标准输入给出的。所有输入值都是整数。
N M A_1 B_1 C_1 P_1 \vdots A_M B_M C_M P_M
出力
标准输出所需的最小金额
输出为 1 行。然而,无论你如何改变道路的颜色,机器人都无法穿过路口。 N ,请改为
输出 -1 。
制約
- 2 \leqq N \leqq 100\,000.
- 1 \leqq M \leqq 200\,000.
- 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
- (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M).
- 1 \leqq C_i \leqq M (1 \leqq i \leqq M).
- 1 \leqq P_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M).
小課題
- (34 点) N \leqq 1\,000,M \leqq 2\,000.
- (24 点) P_i = 1 (1 \leqq i \leqq M).
- (42 点)没有额外的限制。
入力例 1
4 6 1 4 4 4 3 4 1 3 1 3 4 4 2 4 3 1 2 3 3 2 1 2 4 2
出力例 1
3
1 米奇圆 4 颜色 颜色来自 3 重新绘制为 4 , 将其重新绘制为2 米奇圆 6 颜色 颜色来自 4 重新绘制为 2 。总计 3 花费日元。
结果,交集 给机器人上色 1 通过命令 2 ,机器人移动到交叉路口。 您可以将其移至 2 。接下来,给机器人上色。 您可以将其移至 4 ,机器人移动到交叉路口。 您可以将其移至 4 。
2 将机器人移动到圆圈下方的交叉点 由于无法移动到 4 , 输出3 。
入力例 2
5 2 1 4 1 2 3 5 1 4
出力例 2
-1
无论你如何重新粉刷道路,你都可以将机器人移动到十字路口。 它无法移动到 5 。因此,-1 。
入力例 3
5 7 2 3 7 1 1 4 5 1 4 5 3 1 3 4 7 1 2 4 3 1 3 5 6 1 1 2 5 1
出力例 3
1
此输入示例是一个小作业。 2 满足约束。 给出了
入力例 4
13 21 7 10 4 4 3 6 4 7 8 10 4 5 3 9 2 5 1 4 4 5 2 6 4 2 3 11 2 2 3 8 16 2 8 11 16 1 6 10 4 14 6 8 16 6 9 12 16 5 5 13 4 6 1 12 4 7 2 4 4 18 2 9 4 10 2 12 4 6 10 13 4 28 5 7 2 5 5 11 2 16 7 13 4 20
出力例 4
7