分数: 400 分
问题陈述
高桥是一家建筑公司的总裁,负责开发一个群岛,该群岛包括 N 偏远岛屿。每个岛屿的编号为 1 to N.
高桥被分配了一个项目,使居民能够通过桥梁在任意一对岛屿之间旅行。目前,有 M 桥梁建设建议。的 i第提案 (1 \leq i \leq M) 允许建造一座双向连接两个不同岛屿的桥梁 U_i 和 V_i。建造这座桥的费用是 C_i 一万日元。请注意,可能有多个提案连接同一对岛屿。
高桥想选择其中一些 M 提案(每个提案最多只能选择一次)建造桥梁并连接所有岛屿。所有岛屿都是相连的,这意味着对于任何两个岛屿,都可以通过穿过一系列已建桥梁从一个岛屿前往另一个岛屿。特别是,当 N = 1,不需修建任何桥梁,岛屿相连,总成本最小为 0.
由于公司的预算有限,他需要找到实现这一目标的最小总成本。这里,总成本是指所选提案的成本之和。
如果可以连接所有岛屿,则以整数形式输出最小总成本(单位为万日元)。如果不可能,则输出 -1.
约束
- 1 \leq N \leq 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq U_i \leq N
- 1 \leq V_i \leq N
- U_i \neq V_i
- 1 \leq C_i \leq 10^9
- 所有输入值均为整数
输入
N M U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
- 第一行包含岛屿数量 N 桥梁建设提案数量 M,用空格分隔。
- 以下 M 行每行描述一个提案: i第行 (1 \leq i \leq M) 包含两个岛屿的编号 U_i, V_i 由 i第提案和成本 C_i,用空格分隔。
输出
在单行上输出连接所有岛屿所需的最小总成本(万日元)作为整数。如果无法连接所有岛屿,则输出 -1。请注意,答案可能不适合 32 位整数的范围。
示例输入 1
4 5 1 2 3 1 3 5 2 3 4 2 4 6 3 4 2
示例输出 1
9
示例输入 2
3 1 1 2 100
示例输出 2
-1
示例输入 3
6 9 1 2 10 1 3 15 2 3 5 2 4 20 3 4 8 4 5 12 4 6 18 5 6 7 1 6 30
示例输出 3
42