D - 離島を結ぶ橋 解説 /

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

配点 : 400 点

問題文

高橋君は、N 個の離島からなる諸島の開発を担当する建設会社の社長です。それぞれの島には 1 から N までの番号が付けられています。

高橋君は、住民がどの島からどの島へも橋を経由して行き来できるようにするプロジェクトを任されました。現在、M 個の橋の建設案があり、i 番目の案 (1 \leq i \leq M) では、異なる 2 つの島 U_i と島 V_i を双方向に結ぶ橋を建設できます。この橋を建設するには C_i 万円のコストがかかります。なお、同じ 2 つの島を結ぶ建設案が複数存在することもあります。

高橋君は、これらの M 個の建設案の中からいくつかを選んで（各建設案は高々 1 回しか選べません）橋を建設し、すべての島を連結にしたいと考えています。すべての島が連結であるとは、どの 2 つの島の間についても、建設した橋をいくつか順に経由して一方からもう一方へ移動できることを意味します。特に、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
  • 1 行目には、島の数 N と橋の建設案の数 M が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目の建設案で結ぶ 2 つの島の番号 U_i, V_i およびコスト C_i がスペース区切りで与えられる。

出力

すべての島を連結にするために必要な最小総コスト（万円）を整数で 1 行に出力せよ。連結にすることが不可能な場合は -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

Score : 400 pts

Problem Statement

Takahashi is the president of a construction company in charge of developing an archipelago consisting of N remote islands. Each island is numbered from 1 to N.

Takahashi has been assigned a project to enable residents to travel between any pair of islands via bridges. Currently, there are M bridge construction proposals. The i-th proposal (1 \leq i \leq M) allows building a bridge that bidirectionally connects two distinct islands U_i and V_i. The cost to build this bridge is C_i ten-thousand yen. Note that there may be multiple proposals connecting the same pair of islands.

Takahashi wants to select some of these M proposals (each proposal can be selected at most once) to build bridges and make all islands connected. All islands being connected means that for any two islands, it is possible to travel from one to the other by traversing some sequence of built bridges. In particular, when N = 1, the islands are connected without building any bridges, and the minimum total cost is 0.

Since the company's budget is limited, he needs to find the minimum total cost to achieve this goal. Here, the total cost refers to the sum of the costs of the selected proposals.

If it is possible to connect all islands, output the minimum total cost (in ten-thousand yen) as an integer. If it is impossible, output -1.

Constraints

  • 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
  • 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
  • The first line contains the number of islands N and the number of bridge construction proposals M, separated by a space.
  • The following M lines each describe a proposal: the i-th line (1 \leq i \leq M) contains the numbers of the two islands U_i, V_i connected by the i-th proposal and the cost C_i, separated by spaces.

Output

Output on a single line the minimum total cost (in ten-thousand yen) as an integer required to connect all islands. If it is impossible to connect all islands, output -1. Note that the answer may not fit within the range of a 32-bit integer.

Sample Input 1

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

Sample Output 1

9

Sample Input 2

3 1
1 2 100

Sample Output 2

-1

Sample Input 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

Sample Output 3

42