TopCoder

Thumb img 0133
WTF!
我好廢啦晡賴補

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

56.2% (9/16)

Tags

Description

小魯:「7122您好,我是小魯,是個高中生偵探,自從上次跟著小賤去遊樂園後..........,真相永遠只有一個!!!」
覺醒的7122:「說吧,你想從我這邊得到什麼,自從我的好友死去後我已經沒剩下什麼東西了,唯一剩下的就是結衣了,還好有他照顧我,不然...那個死神肯定會再回來的。」
小魯:「放心好了,我會跟結衣會一起保護你的!!說到那個死神,我就是來問有關這件事你的遭遇。」
覺醒的7122:「恩...我想想...那天晚上,我和好友,聽說就是上一個死掉的那傢伙,一起去喝完酒準備要回家,然後在路上看到不知何時出現的奇怪的人站在他的背後,然後他就倒了下去,倒下的瞬間奇怪的人就消失不見,我嚇個半死,然後感覺後面好像有人,之後就失去意識了。」
覺醒的7122:「隱隱約約在失去意識前有發覺有人來了,說了一串奇怪的話吧。」
覺醒的7122:「咳,咳,我要休息了,呼嚕嚕嚕嚕嚕。」
(小魯在心裡想著,這樣我還是什麼都不知道啊...)
這時發現7122好像手裡握著一個東西,打開一看好像是一張地圖。

小魯:「結衣結衣,你知道這是什麼嗎?」
結衣:「恩...我研究一下。」
結衣:「好像是在標註某個人的位置,啊,這個圖有陷阱!」
結衣:「仔細看這張圖,簡單來說它包含了$N$個陷阱,並且以$M$條道路連接著它們,每條道路的長度都不盡相同,每次處發陷阱時必須選擇一條道路發動,陷阱的威力便是選到的這條道路長度加上另外$N-2$條道路的長度和,注意,總共選到的這$N-1$條道路必須將$N$個點完全連接起來,換句話說,任一點$a$到另一點$b$一定有只經過選取道路的路徑,而且你必須選擇使這$N-1$條道路長度總和最小的方案!」
聰明如你,心想這雖然聽起來有點複雜,不過不是很簡單嗎,就____就好了嘛,於是瞬間寫了一個程式秒了這到陷阱,繼續啟程他的冒險苦旅。

Input Format

輸入第一行包含兩個正整數$N,M(1\le N\le 2\times 10^ 5,N-1\le M \le 2\times 10^ 5)$,代表地圖上的陷阱數量以及道路的數量。
接著$M$行每行包含兩個整數$u_i,v_i,w_i(1\le u,_iv_i\le N,u_i\neq v_i,1\le w_i\le 10^ 9)$,代表第$i$條邊的從編號$u_i$的陷阱連到編號$v_i$的陷阱,長度為$w_i$。

For testdata 0~3 (Score: 8) : $N\le 10,M\le 15$
For testdata 4~19 (Score: 20) : $N\le 100,M\le 3000$
For testdata 20~24 (Score: 12) : $N\le 2\times 10^ 5,M=N-1$
For testdata 25~57 (Score: 60) : $N\le 2\times 10^ 5,M\le 2\times 10^ 5$

Output Format

輸出$M$,第$i$行代表選擇第$i$條道路發動陷阱時的威力。

Sample Input

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

Sample Output

9
8
11
8
8
8
9

Hints

Problem Source

Adopted from Codeforces
Set by waynetu
Description by 汁廣

Subtasks

For Testdata: 0 ~ 3, Score: 8
For Testdata: 4 ~ 19, Score: 20
For Testdata: 20 ~ 24, Score: 12
For Testdata: 25 ~ 45, Score: 17
For Testdata: 46 ~ 57, Score: 43
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 1000 131072 65536
2 1000 131072 65536
3 1000 131072 65536
4 1000 131072 65536
5 1000 131072 65536
6 1000 131072 65536
7 1000 131072 65536
8 1000 131072 65536
9 1000 131072 65536
10 1000 131072 65536
11 1000 131072 65536
12 1000 131072 65536
13 1000 131072 65536
14 1000 131072 65536
15 1000 131072 65536
16 1000 131072 65536
17 1000 131072 65536
18 1000 131072 65536
19 1000 131072 65536
20 1000 131072 65536
21 1000 131072 65536
22 1000 131072 65536
23 1000 131072 65536
24 1000 131072 65536
25 1000 131072 65536
26 1000 131072 65536
27 1000 131072 65536
28 1000 131072 65536
29 1000 131072 65536
30 1000 131072 65536
31 1000 131072 65536
32 1000 131072 65536
33 1000 131072 65536
34 1000 131072 65536
35 1000 131072 65536
36 1000 131072 65536
37 1000 131072 65536
38 1000 131072 65536
39 1000 131072 65536
40 1000 131072 65536
41 1000 131072 65536
42 1000 131072 65536
43 1000 131072 65536
44 1000 131072 65536
45 1000 131072 65536
46 1000 131072 65536
47 1000 131072 65536
48 1000 131072 65536
49 1000 131072 65536
50 1000 131072 65536
51 1000 131072 65536
52 1000 131072 65536
53 1000 131072 65536
54 1000 131072 65536
55 1000 131072 65536
56 1000 131072 65536
57 1000 131072 65536