B67 - Max MST Editorial /

Time Limit: 1 sec / Memory Limit: 1024 MB

配点: 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

321