麻衣身為一個當紅演員，要在全國四處拍片是很正常的事情。
咲太為了要偶而去探望女友，有一張國內鐵路圖也是一件很正常的事情。
身為一個汽車維修員，隨身攜帶扳手也是很正常的事情。。。呃不對，離題了。
總之，打工族咲太為了要偶爾去全國各地探望女友，現在正在努力存錢中。
因為都在花時間打工，沒有時間計算到底從居住地出發到全國各地分別要多少的車資。
保證這張鐵路圖中任兩個城市最多存在一條直接連接的鐵道，也不會有任一條鐵道兩端點是同一城市，而且從咲太的居住地出發一定能到達所有城市。
第一、二行分別有兩個整數 $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 |