TopCoder

Doludu = =
我笨

User's AC Ratio

33.3% (4/12)

Submission's AC Ratio

20.3% (14/69)

Tags

Description

水果王國是一個由 $n$ 座城市以及 $m$ 條連接兩座不同的城市的雙向的道路組成的王國,保證任意兩個點皆能互相抵達。並且任意兩座城市最多只有一條道路連接

水果王國與蔬菜王國兩國關係不好,中間常常有大大小小的戰事發生。有一天,水果王國得到了一個消息:蔬菜王國對水果王國發射了一個飛彈!已知飛彈會恰好摧毀一座城市,並且把所有與這座城市相連的道路一併摧毀。但是水果王國的飛彈預測系統有問題,以至於他們完全不知道飛彈會摧毀哪座城市。

為了因應接下來的戰事,水果王國打算把道路鋪設防護罩,使任何兩座完好的城市都可以互相經過鋪設過防護罩的道路而到達。每條道路鋪設防護罩的價格是 $c_i$。因為防護罩很貴,所以水果王國會希望用最少的價格滿足上面的條件。

現在他們找到了你,想請你幫忙輸出對於每座城市 $i$,假設飛彈已經摧毀了這座城市,水果王國至少要花多少的價格來將剩下的道路鋪設防護罩以滿足上面的條件。要是飛彈摧毀了城市 $i$ 會使水果王國無法滿足條件,請輸出 $-1$。

Input Format

第一行會有兩個整數 $n$, $m$,分別表示城市的數量以及道路的數量
接下來會有 $m$ 行,每行是三個整數 $a_i, \ b_i, \ c_i$,分別代表第 $i$ 條道路連接 $a_i, \ b_i$ 兩座城市,且防護罩的價格是 $c_i$。

對於所有測試資料,滿足 $n \leq 150000$, $m \leq 300000$, $1 \leq a_i, b_i \leq n$, $1 \leq c_i \leq 10^ 9$

Output Format

輸出 $n$ 個整數 $a_i$,分別代表飛彈摧毀了城市 $i$ 的話水果王國需要支付的最小價格。

Sample Input 1

Sample Input 1:
4 4
1 2 3
1 4 5
2 3 6
3 4 8

Sample Input 2:
5 7
1 2 3
2 3 7
2 4 9
5 4 10
5 2 8
4 3 2
4 1 6

Sample Output 1

Sample Output 1:
14 13 8 9

Sample Output 2:
17 18 17 18 11

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~25 $n \leq 2500, m \leq 5000$ 17
3 26~50 $c_i = 1$ 20
4 2~25, 51~77 $n \leq 100000, m \leq 100000$ 42
5 0~107 無其他限制 21

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 5
1 1000 262144 65536 1 5
2 1000 262144 65536 2 4 5
3 1000 262144 65536 2 4 5
4 1000 262144 65536 2 4 5
5 1000 262144 65536 2 4 5
6 1000 262144 65536 2 4 5
7 1000 262144 65536 2 4 5
8 1000 262144 65536 2 4 5
9 1000 262144 65536 2 4 5
10 1000 262144 65536 2 4 5
11 1000 262144 65536 2 4 5
12 1000 262144 65536 2 4 5
13 1000 262144 65536 2 4 5
14 1000 262144 65536 2 4 5
15 1000 262144 65536 2 4 5
16 1000 262144 65536 2 4 5
17 1000 262144 65536 2 4 5
18 1000 262144 65536 2 4 5
19 1000 262144 65536 2 4 5
20 1000 262144 65536 2 4 5
21 1000 262144 65536 2 4 5
22 1000 262144 65536 2 4 5
23 1000 262144 65536 2 4 5
24 1000 262144 65536 2 4 5
25 1000 262144 65536 2 4 5
26 1000 262144 65536 3 5
27 1000 262144 65536 3 5
28 1000 262144 65536 3 5
29 1000 262144 65536 3 5
30 1000 262144 65536 3 5
31 1000 262144 65536 3 5
32 1000 262144 65536 3 5
33 1000 262144 65536 3 5
34 1000 262144 65536 3 5
35 1000 262144 65536 3 5
36 1000 262144 65536 3 5
37 1000 262144 65536 3 5
38 1000 262144 65536 3 5
39 1000 262144 65536 3 5
40 1000 262144 65536 3 5
41 1000 262144 65536 3 5
42 1000 262144 65536 3 5
43 1000 262144 65536 3 5
44 1000 262144 65536 3 5
45 1000 262144 65536 3 5
46 1000 262144 65536 3 5
47 1000 262144 65536 3 5
48 1000 262144 65536 3 5
49 1000 262144 65536 3 5
50 1000 262144 65536 3 5
51 1000 262144 65536 4 5
52 1000 262144 65536 4 5
53 1000 262144 65536 4 5
54 1000 262144 65536 4 5
55 1000 262144 65536 4 5
56 1000 262144 65536 4 5
57 1000 262144 65536 4 5
58 1000 262144 65536 4 5
59 1000 262144 65536 4 5
60 1000 262144 65536 4 5
61 1000 262144 65536 4 5
62 1000 262144 65536 4 5
63 1000 262144 65536 4 5
64 1000 262144 65536 4 5
65 1000 262144 65536 4 5
66 1000 262144 65536 4 5
67 1000 262144 65536 4 5
68 1000 262144 65536 4 5
69 1000 262144 65536 4 5
70 1000 262144 65536 4 5
71 1000 262144 65536 4 5
72 1000 262144 65536 4 5
73 1000 262144 65536 4 5
74 1000 262144 65536 4 5
75 1000 262144 65536 4 5
76 1000 262144 65536 4 5
77 1000 262144 65536 4 5
78 1500 262144 65536 5
79 1500 262144 65536 5
80 1500 262144 65536 5
81 1500 262144 65536 5
82 1500 262144 65536 5
83 1500 262144 65536 5
84 1500 262144 65536 5
85 1500 262144 65536 5
86 1500 262144 65536 5
87 1500 262144 65536 5
88 1500 262144 65536 5
89 1500 262144 65536 5
90 1500 262144 65536 5
91 1500 262144 65536 5
92 1500 262144 65536 5
93 1500 262144 65536 5
94 1500 262144 65536 5
95 1500 262144 65536 5
96 1500 262144 65536 5
97 1500 262144 65536 5
98 1500 262144 65536 5
99 1500 262144 65536 5
100 1500 262144 65536 5
101 1500 262144 65536 5
102 1500 262144 65536 5
103 1500 262144 65536 5
104 1500 262144 65536 5
105 1500 262144 65536 5
106 1500 262144 65536 5
107 1500 262144 65536 5