最小生成樹 (AP325 P-7-12)

輸入一個無向圖 \(G = (V, E, w)\)，其中點以 \(0 \sim n-1\) 編號，而邊的權重是非負整數。計算 \(G\) 的最小生成樹的成本。兩點之間可能有多個邊。

輸入格式

第一行是兩個正整數 \(n\) 與 \(m\)，代表點數與邊數；接下來有 \(m\) 行，每行三個整數 \(u\)、\(v\)、\(w\)，代表一條無向邊 \((u, v)\) 的長度是 \(w\)。

限制

• \(1 \le n \le 10^4\)。
• \(1 \le m \le 10^5\)。
• \(0 \le u, v \le n-1\)，\(u \ne v\)；同一對點之間可能有多條邊。
• \(w\) 是不超過 \(10^4\) 的非負整數。

輸出格式

輸出最小生成樹的成本，如果不存在則輸出 \(-1\)。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

8 10
0 1 6
0 2 4
1 2 5
2 3 9
1 4 1
1 5 1
2 6 2
4 5 3
5 6 8
7 6 1

範例輸出 1

23

範例輸入 2

4 3
2 1 5
1 0 0
0 2 1

範例輸出 2

-1

範例說明

範例一是教材 7.4.3 節說明所用的例子，如下圖：實線是最小生成樹的邊，虛線是沒有挑選的邊；\(8\) 個點的生成樹恰好有 \(7\) 條邊，成本 \(4 + 5 + 9 + 1 + 1 + 2 + 1 = 23\)。

範例二的 \(3\) 號點沒有任何邊，圖不連通，生成樹不存在。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 7 章 P-7-12，第 263 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。