95. 我是要成為海賊王的男人

0 Judge

Code: 0


我是要成為海賊王的男人

題目敘述

你的夢想是創建一個海賊大國,而你有天終於實現了。

身為一個大國,必須能夠管理所有城市,這也代表著城市與城市之間必須有路徑可以相互抵達。

你的大國裡有 $N$ 個城市,但現在沒有任何道路。

因為你很懶惰,你決定請人考察城市與城市之間 $M$ 個可能新建的道路以及其成本。

道路是雙向的,只要你支付相應的成本創建一個道路,就能讓兩端的城市能夠相互抵達。

另外,若城市 $A$ 與城市 $B$ 能相互抵達,且城市 $B$ 與城市 $C$ 能夠相互抵達,則城市 $A$ 與城市 $C$ 也能相互抵達。

你希望用最少的總成本,使得任意兩個城市能夠透過道路直接或間接的相互抵達。

輸入說明

輸入的第一行有兩個整數 $N$, $M$,代表城市的數量與候選的道路數量。

接著有 $M$ 行,每行由三個整數以空白分隔,$W$, $U$, $V$,代表其中一個候選道路是花費 $W$,連結 $U$ 和 $V$ 兩城市。

圖中可能有自環或重邊。

$1 \leq N \leq 10^5$

$1 \leq M \leq 10^5$

$0 \leq W \leq 10^3$

$1 \leq U, V \leq N$

輸出說明

請輸出一個整數,代表最少要多少花費才能將所有道路連接,若不可能,輸出 “IMPOSSIBLE”。

範例輸入

範例輸出


Judge Setting

run-time limit: 1000 ms
memory limit: 32048576 byte
測資數量: 7