index.md

熊本

\begin{figure}[h] \centering \includegraphics[width=5in]{img.jpg} \caption{夏奈向警察問路} \end{figure}

在2016年熊本地震過後，夏奈為了尋找失聯的朋友伊月，而踏上了旅程。
夏奈終於來到伊月所居住的城市，但她不知道伊月在哪，於是她決定搭捷運來探索這種城市。
這座城市的捷運總共有 $N$ 站，$M$ 條鐵道連接兩個車站，所有車站都可透過轉乘到達。
由於夏奈身上的錢有限，她想要先計算從目前所在的車站搭到任何一站至少要花多少錢。
捷運的計費方式很特別，首先兩站之間的一段路線都有基本價格，而總票價為 $($ $A~\times$經過的路線數 $+B\times$經過路線的基本價格總和 $)$，如果有多種不同的路徑，則以最低價的方法計算。
請問從目前所在編號為 $S$ 的車站搭到每一站的價格是多少。

\clearpage

輸入

第一行有五個整數 $N, M, A, B, S$，
接下來 $M$ 行，每行有三個整數 $u_i, v_i, w_i$，表示從 $u_i$ 到 $v_i$ 有一條鐵道連接，且基本價格為 $w_i$。

輸出

輸出 $N$ 個整數，依序為 $S$ 到編號 $1, 2, \cdots, N$ 的票價，以空白隔開，行尾也請輸出空白並換行。
起訖站相同則為 $0$。

輸入限制

• $1 \le N \le 10^5$
• $1 \le M \le 5 \times 10^5$
• $1 \le S, u_i, v_i \le N$
• $0 \le A, B \le 10^6$
• $1 \le w_i \le 10^6$

子任務

\subtasks

\clearpage

範例輸入1

5 4 0 1 3
3 1 1
3 2 2
1 4 3
1 5 4

範例輸出1

1 2 0 4 5

範例輸入2

5 4 1 1 3
3 1 1
3 2 2
1 4 3
1 5 4

範例輸出2

2 3 0 6 7

範例輸入3

4 5 2 3 1
1 2 11
1 3 13
1 4 17
2 4 19
3 4 23

範例輸出3

0 35 41 53