Problem : 140 - 海綿寶寶之偷賣美味蟹堡(最小生成樹)

Problem Statistics

Solved Member: 48　　Submission: 155　　User Tried: 50

Statement:

這是正經八百小姐，不過因為太醜了所以只放黑白照。

正經八百小姐來攻擊蟹堡王了，因為丈夫艾爾是警察讓她可以禁賣美味蟹堡！
這時候蟹老闆急中生智，他想要在海綿寶寶的鳳梨屋裡面偷賣美味蟹堡，好刺激>///<！
蟹老闆怕客戶不知道他們在鳳梨屋賣蟹堡，所以請海綿寶寶「打電話」通知大家。
海綿寶寶可以自己去聯絡朋友，也可以利用已經通知的朋友再聯絡他所知道的人。〈一定要打電話通知〉
不巧，比奇堡的電信業者很黑，每家費率算法都不一樣，任意兩人之間打電話的費用不一定相同。所以希望能找到一種最便宜又可以聯絡到大家的方法。
我們將這 n 個人由 1 編號到 n，其中海綿寶寶的編號為 1。我們希望其他 n-1 個人都被通知，並且告訴你 m 種可行的聯絡方式。
海綿寶寶要如何借助朋友的力量，用最少的花費把消息傳遞出去呢？請你告訴他們吧！

Input:Output:

第一行有兩個數字n, m(n≦50000, m≦200000)，分別代表n個需要被通知的人數(包含編號為1的海綿寶寶)和m種可以互相聯絡的對應關係。
接下來有m行，每一行有三個數字a, b, c(1≦a,b,≦n, -10000≦c≦10000)，代表編號 a 的人和編號 b 的人互相知道對方的電話。若通話則會花費 c 。
在上述 m 行中沒有提到的聯絡方式我們視為他們之間沒有對方的電話號碼。

輸出一個數字，代表最少花費的值。
若無法聯絡到所有人請輸出-1。

Sample Input:Sample Output:

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

HINT:

我愛海綿寶寶>///<

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1-1	2000ms	65536kb	10
1-2	2000ms	65536kb
2-1	2000ms	65536kb	10
2-2	2000ms	65536kb
3-1	2000ms	65536kb	10
3-2	2000ms	65536kb
4-1	2000ms	65536kb	10
4-2	2000ms	65536kb
5-1	2000ms	65536kb	10
5-2	2000ms	65536kb
6-1	2000ms	65536kb	10
6-2	2000ms	65536kb
7-1	2000ms	65536kb	10
7-2	2000ms	65536kb
8-1	2000ms	65536kb	10
8-2	2000ms	65536kb
9-1	2000ms	65536kb	10
9-2	2000ms	65536kb
10-1	2000ms	65536kb	10
10-2	2000ms	65536kb