← 返回题目列表

AtCoder · tessoku_book_bo

A67. MST(最小生成树)

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

配点: 1000 点

問題文

頂点数 N、辺数 M 的图表。在顶部 边的编号最大为 1 减去 N 。 i 是顶点 是 A_i 和 按字典顺序比较 B_i 有一条 C_i 一侧。该图的 求最小全域木中边长的总和。

制約

  • 2 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 1 \leq A_i \lt B_i \leq N
  • i\neq j 如果 (A_i,B_i) \neq (A_j,B_j)
  • 1 \leq C_i \leq 10000
  • 给定的图形已连接
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

请输出最小生成树的边长之和。 有多少个数字可以被


入力例 1

7 9
1 2 12
1 3 10
2 6 160
2 7 15
3 4 1
3 5 4
4 5 3
4 6 120
6 7 14

出力例 1

55