TopCoder

Thumb output jddoia
$\huge 南ことり$
$https://www.ototot.com.tw/TIOJ/ \\我要拿牌、去東京、變紅色,那就努力吧 \\ 確かな今よりも新しい夢つかまえたい$

User's AC Ratio

92.0% (80/87)

Submission's AC Ratio

31.9% (165/518)

Description

給你一個加權的無向圖(weighted undirected graph),請問這個圖的最小生成樹(minimum spanning tree)的權重和為多少?

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料的第一列有兩個正整數n,m(1<=n<=10,000;1<=m<=1,000,000),代表該圖的點數和邊數。
頂點的編號從1到n。
接下來有m列,每列用三個整數i,j,c(1<=i,j<=n;1<=c<=1,000)描述一條邊,i,j為兩個端點的編號,c為其權重。
當n=m=0時代表輸入結束。

Output Format

對於每筆測試資料,請輸出最小生成樹的權重和。如果圖不連通,請輸出-1。

Sample Input

3 3
1 2 5
2 3 5
3 1 10
4 2
1 2 5
2 3 5
0 0

Sample Output

10
-1

Hints

Problem Source

原TIOJ1211 / TIOJ 2008例行賽03 (prob C)。經典問題練習。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 65536
1 10000 65536 65536
2 10000 65536 65536