가격표

바이트오티아에서 철도는 예로부터 가장 인기 있는 교통수단이다. 이 나라의 도시 $n$개 가운데 $m$쌍이 바이트오티아 국영철도(BSR)의 선로로 직접 이어져 있다. 선로는 도시 안에서만 만나며, 다리 위나 터널 속을 지나기도 한다. 선로로 직접 연결된 두 도시 사이를 오가는 표 한 장의 값은 $a$ 바이탈러이다.

이제 교통 시장에 변화가 생겼다. BSR에 새로운 경쟁자 바이트오티아 항공(BA)이 등장한 것이다. 열차가 워낙 편안하기 때문에, BA는 다음 두 조건을 모두 만족하는 두 도시 사이에만 항공편을 운항한다.

• 두 도시가 선로로 직접 이어져 있지 않고,
• 두 도시를 잇는 가장 값싼 철도 경로가 환승을 정확히 한 번 필요로 한다. 즉 가장 짧은 철도 경로가 선로 구간 정확히 두 개로 이루어진다.

이러한 항공편 한 편의 값은 $b$ 바이탈러이다.

철도나 항공 연결을 순서대로 이어 붙인 것을 경로라 한다. 철도든 항공이든 모든 연결은 양방향이다. 도시 $k$에서 출발하여 각 도시에 이르는 가장 값싼 경로의 비용을 구하여라.

첫째 줄에 다섯 정수 $n$, $m$, $k$, $a$, $b$가 공백 하나로 구분되어 주어진다 ($2 \le n \le 100{,}000$, $1 \le m \le 100{,}000$, $1 \le k \le n$, $1 \le a, b \le 1{,}000$). $n$은 도시의 수(도시는 $1$번부터 $n$번까지 번호가 매겨진다), $m$은 직접 연결된 철도 노선의 수, $k$는 출발 도시, $a$는 철도 연결 하나의 값, $b$는 항공편 하나의 값이다.

다음 $m$개의 줄에는 각각 두 정수 $u_i$와 $v_i$가 주어지며 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$), 도시 $u_i$와 $v_i$가 선로로 직접 이어져 있음을 뜻한다.

모든 도시는 도시 $k$에서 철도로 갈 수 있다.

$n$개의 줄을 출력한다. $i$번째 줄($i = 1, 2, \ldots, n$)에는 도시 $k$에서 도시 $i$로 가는 가장 값싼 경로의 비용을 정수 하나로 출력한다. 특히 $k$번째 줄에는 $0$을 출력한다.

도시 $1$에서 도시 $5$로 가는 가장 값싼 경로는 도시 $3$ 또는 도시 $4$를 거친다. 두 경우 모두 철도 연결 하나와 항공편 하나로 이루어진다.