電腦教室的最省佈線

題目敘述

電腦教室裡有 n 台電腦，編號 1 到 n。目前有 m 條可以拉的網路線，每條連接兩台電腦，並有各自的費用。請挑選其中一部分，讓全部成員直接或間接連通，且總權重最小（也就是最小生成樹），輸出這個最小總權重。如果無論怎麼選都無法全部連通，輸出 −1。

輸入格式

• 第一行：兩個整數 n 與 m。
• 接下來 m 行，每行三個整數 u v w，表示 u 與 v 之間有一條權重為 w 的邊。

輸出格式

• 一個整數：最小總權重，或是 −1。

限制

• 1 ≤ n ≤ 100
• 0 ≤ m ≤ 500
• 1 ≤ w ≤ 1000

範例

範例 1

輸入

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

輸出

6

範例 2

輸入

2 1
1 2 7

輸出

7

說明

• 範例 2 只有兩個頂點與一條權重 7 的邊，所以答案是 7。