CF1149D.Abandoning Roads

Codefortia is a small island country located somewhere in the West Pacific. It consists of $n$ settlements connected by $m$ bidirectional gravel roads. Curiously enough, the beliefs of the inhabitants require the time needed to pass each road to be equal either to $a$ or $b$ seconds. It's guaranteed that one can go between any pair of settlements by following a sequence of roads.

Codefortia was recently struck by the financial crisis. Therefore, the king decided to abandon some of the roads so that:

• it will be possible to travel between each pair of cities using the remaining roads only,
• the sum of times required to pass each remaining road will be minimum possible (in other words, remaining roads must form minimum spanning tree, using the time to pass the road as its weight),
• among all the plans minimizing the sum of times above, the time required to travel between the king's residence (in settlement $1$) and the parliament house (in settlement $p$) using the remaining roads only will be minimum possible.

The king, however, forgot where the parliament house was. For each settlement $p = 1, 2, \dots, n$, can you tell what is the minimum time required to travel between the king's residence and the parliament house (located in settlement $p$) after some roads are abandoned?

Codefortia 是西太平洋某处的一个小岛国，由 $n$ 个聚居地和 $m$ 条双向碎石道路组成。有趣的是，当地居民的信仰要求：每条道路的通行时间恰好为 $a$ 秒或 $b$ 秒。保证任意两个聚居地之间均可通过若干条道路相互到达。

最近，Codefortia 遭遇了金融危机。因此，国王决定废弃部分道路，使得：

• 仅利用剩余的道路，仍可在任意两个城市之间通行；
• 剩余道路的通行时间总和尽可能小（即：剩余道路构成一棵最小生成树，边权为对应道路的通行时间）；
• 在所有满足上述总时间最小化的方案中，从国王住所（位于聚居地 $1$）到议会大厦（位于聚居地 $p$）仅经由剩余道路通行所需的时间最小。

然而，国王却忘记了议会大厦的确切位置。请对每个聚居地 $p = 1, 2, \dots, n$，计算在废弃部分道路后，从国王住所到位于聚居地 $p$ 的议会大厦的最短通行时间。

The first line of the input contains four integers $n$, $m$, $a$ and $b$ ($2 \leq n \leq 70$, $n - 1 \leq m \leq 200$, $1 \leq a \lt b \leq 10^7$) — the number of settlements and gravel roads in Codefortia, and two possible travel times. Each of the following lines contains three integers $u, v, c$ ($1 \leq u, v \leq n$, $u \neq v$, $c \in {a, b}$) denoting a single gravel road between the settlements $u$ and $v$, which requires $c$ minutes to travel.

You can assume that the road network is connected and has no loops or multiedges.

输入的第一行包含四个整数 $n$、$m$、$a$ 和 $b$（$2 \leq n \leq 70$，$n - 1 \leq m \leq 200$，$1 \leq a \lt b \leq 10^7$），分别表示 Codefortia 中的聚居地数量、碎石路数量以及两种可能的通行时间。接下来的每一行包含三个整数 $u$、$v$、$c$（$1 \leq u, v \leq n$，$u \neq v$，$c \in \{a, b\}$），表示一条连接聚居地 $u$ 和 $v$ 的碎石路，通行该道路需 $c$ 分钟。

可以假设道路网络是连通的，且不含自环或重边。

Output a single line containing $n$ integers. The $p$-th of them should denote the minimum possible time required to travel from $1$ to $p$ after the selected roads are abandoned. Note that for each $p$ you can abandon a different set of roads.

输出一行，包含 $n$ 个整数。其中第 $p$ 个整数表示在舍弃若干条道路后，从节点 $1$ 到节点 $p$ 所需的最少时间。注意：对每个 $p$，可舍弃的道路集合可以不同。

The minimum possible sum of times required to pass each road in the first example is $85$ — exactly one of the roads with passing time $25$ must be abandoned. Note that after one of these roads is abandoned, it's now impossible to travel between settlements $1$ and $3$ in time $50$.

第一个示例中，通过每条道路所需的最短总时间为 $85$ —— 恰好需要放弃一条通行时间为 $25$ 的道路。注意：在放弃其中一条该道路后，城镇 $1$ 与城镇 $3$ 之间便无法在时间 $50$ 内相互到达了。