麻衣身為一個當紅演員,要在全國四處拍片是很正常的事情。
咲太為了要偶而去探望女友,有一張國內鐵路圖也是一件很正常的事情。
身為一個汽車維修員,隨身攜帶扳手也是很正常的事情。。。呃不對,離題了。
總之,打工族咲太為了要偶爾去全國各地探望女友,現在正在努力存錢中。
因為都在花時間打工,沒有時間計算到底從居住地出發到全國各地分別要多少的車資。
保證這張鐵路圖中任兩個城市最多存在一條直接連接的鐵道,也不會有任一條鐵道兩端點是同一城市,而且從咲太的居住地出發一定能到達所有城市。
第一、二行分別有兩個整數 $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$
輸出 $N$ 個整數,每個整數之間由一個空格隔開,第 $i$ 個整數代表從居住地出發,到達第 $i$ 個城市所需要的車資。
保證鐵路圖任意兩個城市至少有一條路線直接或間接連接。
No. | Testdata Range | Score |
---|---|---|
1 | 0~9 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 |