← 返回题目列表

Codeforces · 1149/D

D. 废弃道路

中文机器翻译题面 查看原题

Codefortia 是位于西太平洋某处的一个小岛国。它由 $$$n$$$ 定居点组成,由 $$$m$$$ 双向碎石路连接。奇怪的是,居民的信念要求通过每条道路所需的时间等于 $$$a$$$ 或 $$$b$$$ 秒。保证人们可以沿着一系列道路在任意一对定居点之间移动。

Codefortia 最近受到金融危机的打击。因此,国王决定放弃一些道路,以便:

- 可以仅使用剩余的道路在每对城市之间行驶,
- 通过剩余每条道路所需的时间总和将尽可能最小(换句话说,剩余道路必须形成最小生成树,以通过道路的时间作为其权重),
- 在最小化上述时间总和的所有计划中,仅使用剩余道路在国王住所(定居点 $$$1$$$)和议会大厦(定居点 $$$p$$$)之间行驶所需的时间将尽可能最小。

然而,国王忘记了议会大厦在哪里。对于每个定居点 $$$p = 1, 2, \dots, n$$$,您能否说出在一些道路被废弃后,从国王住所到议会大厦(位于定居点 $$$p$$$)之间行驶所需的最短时间是多少?

输入

输入的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \leq n \leq 70$$$, $$$n - 1 \leq m \leq 200$$$, $$$1 \leq a < b \leq 10^7$$$) — Codefortia 的定居点和碎石路数量,以及两个可能的旅行时间。以下每一行包含三个整数 $$$u, v, c$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$c \in \{a, b\}$$$),表示定居点 $$$u$$$ 和 $$$v$$$ 之间的一条碎石路,需要 $$$c$$$ 分钟才能行驶。

您可以假设道路网是连通的并且没有环路或多边边。

输出

输出包含 $$$n$$$ 整数的单行。其中第 $$$p$$$ 应该表示在选定的道路被放弃后从 $$$1$$$ 行驶到 $$$p$$$ 所需的最短可能时间。请注意,对于每个 $$$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

注意

第一个示例中通过每条道路所需的最小可能时间总和为 $$$85$$$ — 必须放弃其中一条通过时间为 $$$25$$$ 的道路。请注意,其中一条道路被废弃后,现在不可能在 $$$50$$$ 时间内在 $$$1$$$ 和 $$$3$$$ 之间行驶。