校園步行距離

題目敘述

校園裡有 n 棟建築，編號 1 到 n，其中有 m 條雙向步道，每條步道都有一個正的長度。新生從 s 號建築出發，想知道走到每一棟建築至少要走多遠。

輸出 s 號頂點到編號 1 到 n 每個頂點的最短距離；若無法到達，該位置輸出 −1。

輸入格式

• 第一行有三個整數 n、m、s。
• 接下來 m 行，每行三個整數 u、v、w，表示 u 與 v 之間有一條長度為 w 的無向邊。

輸出格式

輸出一行，包含 n 個以空白隔開的整數，依序為頂點 1 到 n 的最短距離（無法到達則為 −1）。

限制

• 1 ≤ n ≤ 100
• 0 ≤ m ≤ 500
• 1 ≤ w ≤ 1000

範例

範例 1

輸入

4 4 1
1 2 3
2 3 1
1 3 10
3 4 2

輸出

0 3 4 6

範例 2

輸入

2 1 1
1 2 5

輸出

0 5

說明

範例 1 中，頂點 1 經 2 到 3 的距離為 3+1=4，比直接走長度 10 的邊更短。