弃置道路

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

Codefortia 由 $n$ 个居民点和 $m$ 条双向道路组成。每条道路的通行时间恰好为 $a$ 秒或 $b$ 秒，其中 $a<b$。道路网络连通，且没有自环或重边。

国王要弃置一些道路，使剩余道路构成一棵最小生成树。在所有最小生成树中，他还希望从住所 $1$ 到议会所在地 $p$ 的通行时间尽可能短。

对于每个 $p=1,2,\ldots,n$，请独立选择最合适的最小生成树，并输出从 $1$ 到 $p$ 的最小可能树上距离。不同的 $p$ 可以选择不同的最小生成树。

输入格式

第一行包含四个整数 $n,m,a,b$。

接下来 $m$ 行，每行包含三个整数 $u,v,c$，表示一条连接 $u$ 与 $v$、通行时间为 $c$ 的无向道路。

保证：

• $2\le n\le70$；
• $n-1\le m\le200$；
• $1\le a<b\le10^7$；
• $c\in\{a,b\}$；
• 图连通，没有自环或重边。

输出格式

输出一行 $n$ 个整数。第 $p$ 个整数表示：在所有最小生成树中，从 $1$ 到 $p$ 的树上距离的最小值。

样例输入 1

5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20

样例输出 1

0 25 60 40 20

样例输入 2

6 7 13 22
1 2 13
2 3 13
1 4 22
3 4 13
4 5 13
5 6 13
6 1 13

样例输出 2

0 13 26 39 26 13

数据范围

对于所有数据，$2\le n\le70$，$n-1\le m\le200$，$1\le a<b\le10^7$，且每条边权均属于 $\{a,b\}$。