题目描述

给定一个 $n$ 个点，$m$ 条边的无向联通图，每条边的权值均为 $a$。

在原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边，边的权值均为 $b$。

给定一个起始节点$k$，求在上述操作后，$k$到所有节点的最短路径。

输入格式

第一行五个正整数：$n,m,k,a,b$ ，表示图的点数，初始的边数，起始节点和两种边的权值。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$ ，代表原图中的一条无向边（ $1 \leq u_i ,v_i \leq n$ ， $u_i \neq v_i$ ）。

保证原图联通，即在原图中从 $k$ 节点出发可以到达所有节点。

输出格式

输出共有 $n$ 行。

每行一个整数，第 $i$ 行的数代表操作后 $k$ 节点和 $i$ 节点间的最短路。

注意，在第 $k$ 行你应该输出一个整数 $0$ 。

样例

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

0
3
3
2
5

数据范围与提示

对于 $30\%$ 的数据，保证 $2 \leq n \leq 700$，$1 \leq m \leq 700$。

对于 $100\%$ 的数据，保证 $2 \leq n \leq 100000$，$1 \leq m \leq 100000$，$1 \leq k \leq n$，$1 \leq a,b \leq 1000$。