← 返回题目列表

AtCoder · awc0064_d

D. 连接偏远岛屿的桥梁

中文机器翻译题面 查看原题

分数: 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