TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

90.0% (9/10)

Tags

Description

GG 戰隊的基地中有 N 位選手,可以把基地看做是一張 N 個點 M 條邊的圖,編號 i 的頂點代表第 i 位選手的休息室的所在位置。

每條邊代表連接兩個休息室的通道(可能是同一個休息室),且邊權代表通道的長度,保證所有的邊權恰好是 1M 的一個排列。

GG 戰隊中選手的編號是按照輩分排序的,也就是說編號越小的選手年紀越大。具體來說,若 i<j ,則選手 i 是選手 j 的一個哥。

現在如果選手 i 想要為自己的一個哥倒水,他就會從自己的休息室開始經過通道數次到達那位哥的休息室。

每個選手會選擇能使路程疲累程度最低的哥來為他倒水,而一個路程的疲累程度是經過的通道中最長的長度。

(因為到達一個哥之前經過的都是弟弟的休息室,所以可以在那裡休息到疲累完全消除,於是疲累程度就只跟經過的最長通道有關)

對除了 1 號選手(哥的哥的 的哥)以外的其他 N1 個選手,求出他們想為自己的一個哥倒水的話所需最小的疲累程度。

Input Format

輸入的第一行有兩個正整數 N,M

接下來的 M 行每行有三個用空白分開的整數 ui,vi,wi ,代表第 i 條邊連接點 ui 和點 vi 且邊權為 wi

  • 1N5×105,1M106
  • 1ui,viN,1wiM
  • wiwj
  • 圖是無向的,且保證連通

Output Format

輸出 N1 行整數,第 i 行的整數代表編號為 i+1 的選手為他的哥倒水最小的疲累程度。

Sample Input 1

3 3
1 2 3
2 3 1
3 1 2

Sample Output 1

2
1

Sample Input 2

8 8
1 2 8
2 4 6
2 3 1
5 1 3
5 6 5
3 7 2
4 8 7
6 8 4

Sample Output 2

7
1
6
3
5
2
4

Hints

Problem Source

IOICamp 2022 Day3 pD

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2
1 3000 262144 65536 1 2
2 3000 262144 65536 2
3 3000 262144 65536 2
4 3000 262144 65536 2
5 3000 262144 65536 2
6 3000 262144 65536 2
7 3000 262144 65536 2
8 3000 262144 65536 2
9 3000 262144 65536 2
10 3000 262144 65536 2
11 3000 262144 65536 2