User's AC Ratio

66.7% (28/42)

Submission's AC Ratio

12.1% (61/505)

Description

麻衣身為一個當紅演員,要在全國四處拍片是很正常的事情。
咲太為了要偶而去探望女友,有一張國內鐵路圖也是一件很正常的事情。
身為一個汽車維修員,隨身攜帶扳手也是很正常的事情。。。呃不對,離題了。
總之,打工族咲太為了要偶爾去全國各地探望女友,現在正在努力存錢中。
因為都在花時間打工,沒有時間計算到底從居住地出發到全國各地分別要多少的車資。

保證這張鐵路圖中任兩個城市最多存在一條直接連接的鐵道,也不會有任一條鐵道兩端點是同一城市,而且從咲太的居住地出發一定能到達所有城市。

Input Format

第一、二行分別有兩個整數 $N, M$,代表鐵路圖上有多少城市,以及有多少條鐵道連接兩個城市。
接著開始有 $M$ 行,每行三個整數 $u, v, w$ ,分別代表來往 $u$ 與 $v$ 的鐵路需要花費 $w$ 元的車資。
城市編號由 $0 \sim N - 1$ 共 $N$ 個城市 ,其中 $0$ 號城市代表咲太的居住地。
保證所有測資$1 \le N \le 10^ 5, N - 1 \le M \le \min( 3 \times 10^ 5, \frac{N \times ( N - 1 )}{2}), 0 \le u, v < N, 0 \le w \le 10^ 9$

Output Format

輸出 $N$ 個整數,每個整數之間由一個空格隔開,第 $i$ 個整數代表從居住地出發,到達第 $i$ 個城市所需要的車資。
保證鐵路圖任意兩個城市至少有一條路線直接或間接連接。

Sample Input 1

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

Sample Output 1

0 6 9 8 7

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1