题目描述

题目译自 XX Olimpiada Informatyczna — I etap Cennik

给定一个 $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$。