Description

铁路一直是 Byteotia 最受欢迎的交通方式。

在这个国家的 $n$ 个城镇中，有 $m$ 对城镇由 Byteotian State Railways (BSR) 的轨道段连接。

这些轨道不会在城镇外交叉，可能会经过风景如画的桥梁和不太风景如画的隧道。

直接通过铁路连接的任意两个城镇之间的票价为 $a$ 比特勒。

目前，Byteotia 的交通市场正在发生变化。

截至目前，BSR 面临着一个新的竞争对手：Byteotian Airlines (BA)。

BA 计划在一些城镇对之间运营航班。

由于 Byteotian 铁路相当舒适，BA 董事会决定只在那些没有直接铁路连接的城镇对之间运营航班。出于经济原因，BA 只会在那些需要恰好一次换乘的城镇之间飞行。

每张此类航班的票价为 $b$ 比特勒。

为了帮助 Byteotia 的市民规划他们的旅行，Byteotian 交通部 (BMT) 决定发行传单，说明所有可能城镇之间的最便宜路线。任意数量的直接铁路或飞机连接的序列被称为路线。名叫 Byteasar 的 BMT 官员被委派准备传单的价格表。

你能帮他写一个程序来确定正确的价格吗？

让我们明确一下，Byteotia 的所有连接，无论是铁路还是飞机，都是双向的。

Input Format

标准输入的第一行包含五个整数，$n$，$m$，$k$，$a$ 和 $b$ ($2\le n\le 100\ 000$, $0\le m\le 100\ 000$, $1\le k\le n$, $1\le a,b\le 1\ 000$)，以单个空格分隔。

数字 $n$ 和 $m$ 分别表示 Byteotia 中的城镇数量和直接铁路连接的数量。

为简化起见，我们将 Byteotia 的城镇编号为 $1$ 到 $n$。其他数字表示：$k$ - 需要确定连接价格的源城镇的编号；$a$ - 直接铁路连接的价格；$b$ - 直接飞机连接的价格。

接下来的 $m$ 行中的每一行包含一对整数 $u_i$ 和 $v_i$ ($1\le u_i,v_i\le n$，$u_i e v_i$ 对于 $i=1,2,\cdots,m$)，以单个空格分隔，指定由轨道直接连接的城镇对的编号。

你可以假设所有城镇都可以通过铁路从编号为 $k$ 的城镇到达。

Output Format

你的程序应输出 $n$ 行到标准输出。

第 $i$ 行（对于 $i=1,2,\cdots,n$）应包含一个整数：

从编号为 $k$ 的城镇到编号为 $i$ 的城镇的最便宜路线的费用。

其中，第 $k$ 行应包含数字 $0$。

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

0
3
3
2
5

Hint

2024/2/4 添加了一部分来自 bzoj 的数据。

题面翻译由 ChatGPT-4o 提供。