1445 . 機器人組裝大賽
TopCoder
Tags
Description
一年一度的機器人組裝大賽又要開始了！
在你面前有 $n$ 塊零件，有些零件之間是可以互相連接的，而連接兩塊零件需要不同的力氣（因為鬆緊度不同的緣故）。
這種機器人要運作的方式相當的簡單，只要把 $n$ 個零件全部連接在一起，它就可以運作了。
當你正在想要如何花費最少力氣完成這個工作時，你突然發現老姜跟皮皮那隊已經設計好了一種可以最省力的連接方法了。
當所有其他參賽者全部都來仿效老姜跟皮皮時，你突然想到，假如你可以設計出一個與眾不同的連接方法的話，一定可以吸引評審的注意力而獲得大賽的冠軍！
但是你也不想花太多力氣，所以雖然你不想跟他們的作品一模一樣，但還是希望花的力氣越少越好。
對了，假如你能順便把老姜跟皮皮花了多少力氣給算出來，說不定還能去和他們炫耀一番呢！
Input Format
本題只有一筆測試資料：
第一行包含兩個正整數 $n, m$ ，
代表零件的數目以及可以互相連接的零件對數。
$0 < n \le 1000 , m \le \frac{n(n-1)}{2}$
接下來有 $m$ 行，
每行有三個數字 $a, b, c$，
代表連接第 $a$ 個組件和第 $b$ 個組件需要花 $c$ 單位的力氣。
注意：$a$ 有可能等於 $b$；$c$ 是非負整數。
Output Format
請輸出兩個以空白隔開的整數，分別代表老姜跟皮皮花了多少力氣和你最少要花多少力氣。保證答案在 long long 範圍內。
若老姜跟皮皮無法將零件全部連接在一起，請輸出 "-1 -1"（不含雙引號）。
若你無法找出跟他們不同的組合方式，第二個數字請輸出 -1。
Sample Input 1
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
Sample Output 1
Hints
老姜跟皮皮把 $(3,4)(2,4)(4,5)(1,2)$連接起來
而你把 $(3,4)(2,4)(1,2)(2,5)$連接起來
※2008/10/08 測資範圍加入,時限修正 by hallogameboy，感謝 peter50216。
2021.04.11 Update: Added $\LaTeX$ by FHVirus
Problem Source
原TIOJ1445 / 建中校內培訓第一次模擬考試。
Problem Setter：hallogameboy、peter50216
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 9 |
| 2 | 1 | 9 |
| 3 | 2 | 9 |
| 4 | 3 | 9 |
| 5 | 4 | 9 |
| 6 | 5 | 9 |
| 7 | 6 | 9 |
| 8 | 7 | 9 |
| 9 | 8 | 9 |
| 10 | 9 | 9 |
| 11 | 10 | 10 |