2288 . 飛彈
TopCoder
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
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
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 |