D - 道路網の整備 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

AtCoder 王国には 1 から N までの番号が付けられた N 個の都市があります。初期状態では、都市間を結ぶ道路はありません。

都市間を結ぶ道路の建設計画が M 個あり、1 から M までの番号が付けられています。計画 i (1 \leq i \leq M) を採用すると、都市 U_i と都市 V_i の間を双方向に通行可能な道路をコスト C_i で建設することができます。

国王である高橋君は、M 個の計画それぞれについて採用するかしないかを決め、相異なるどの 2 つの都市の間も、採用した計画によって建設された道路をいくつかたどって行き来できるようにしたいと考えています。

条件を満たすために採用する計画のコストの総和として考えられる最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • すべての計画を採用したとき、相異なるどの 2 つの都市の間も道路をいくつかたどって行き来できる。
  • 同じ 2 つの都市を結ぶ計画が複数存在することもある（すなわち、ある i \neq j について \{U_i, V_i\} = \{U_j, V_j\} であることがある）。
  • 入力はすべて整数である。

入力

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

出力

採用する計画のコストの総和の最小値を 1 行に出力してください。

入力例 1

4 5
1 2 2
1 3 3
2 3 1
2 4 4
3 4 5

出力例 1

7

入力例 2

3 4
1 2 10
1 2 5
2 3 3
1 3 8

出力例 2

8

入力例 3

8 12
1 2 4
1 3 8
2 3 11
2 4 8
3 5 7
4 5 2
4 6 7
4 7 4
5 7 14
6 7 6
6 8 9
7 8 10

出力例 3

40

入力例 4

12 20
1 2 15
2 3 20
3 4 10
4 5 25
5 6 30
6 7 5
7 8 12
8 9 18
9 10 22
10 11 8
11 12 14
1 4 50
2 5 40
3 6 35
4 7 15
5 8 60
6 9 28
7 10 45
8 11 33
9 12 19

出力例 4

161

入力例 5

2 1
1 2 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

The Kingdom of AtCoder has N cities numbered 1 to N. Initially, there are no roads connecting the cities.

There are M road construction plans, numbered 1 to M. If Plan i (1 \leq i \leq M) is adopted, a bidirectional road can be built between City U_i and City V_i at a cost of C_i.

King Takahashi wants to decide whether to adopt each of the M plans so that it is possible to travel between any two distinct cities by traversing some of the roads built by the adopted plans.

Find the minimum possible total cost of the adopted plans to satisfy this condition.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • N - 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
  • U_i \neq V_i (1 \leq i \leq M)
  • 1 \leq C_i \leq 10^9 (1 \leq i \leq M)
  • If all plans are adopted, it is possible to travel between any two distinct cities by traversing some roads.
  • There may be multiple plans connecting the same two cities (that is, \{U_i, V_i\} = \{U_j, V_j\} may hold for some i \neq j).
  • All input values are integers.

Input

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

Output

Print the minimum possible total cost of the adopted plans in a single line.

Sample Input 1

4 5
1 2 2
1 3 3
2 3 1
2 4 4
3 4 5

Sample Output 1

7

Sample Input 2

3 4
1 2 10
1 2 5
2 3 3
1 3 8

Sample Output 2

8

Sample Input 3

8 12
1 2 4
1 3 8
2 3 11
2 4 8
3 5 7
4 5 2
4 6 7
4 7 4
5 7 14
6 7 6
6 8 9
7 8 10

Sample Output 3

40

Sample Input 4

12 20
1 2 15
2 3 20
3 4 10
4 5 25
5 6 30
6 7 5
7 8 12
8 9 18
9 10 22
10 11 8
11 12 14
1 4 50
2 5 40
3 6 35
4 7 15
5 8 60
6 9 28
7 10 45
8 11 33
9 12 19

Sample Output 4

161

Sample Input 5

2 1
1 2 1000000000

Sample Output 5

1000000000