CF1149D Abandoning Roads

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$），分别表示居民点数量、碎石路数量以及两种可能的通过时间。接下来的 $m$ 行，每行包含三个整数 $u, v, c$（$1 \leq u, v \leq n$，$u \neq v$，$c \in \{a, b\}$），表示一条连接居民点 $u$ 和 $v$ 的碎石路，通过该路需要 $c$ 分钟。 保证道路网络连通，且没有自环或重边。

输出一行包含 $n$ 个整数，第 $p$ 个整数表示在废弃部分道路后，从 $1$ 号居民点到 $p$ 号居民点所需的最短时间的最小可能值。注意，对于每个 $p$，你可以选择不同的废弃道路方案。

在第一个样例中，所有道路通过时间的最小总和为 $85$——必须废弃一条通过时间为 $25$ 的道路。注意，废弃其中一条后，将不再可能在 $50$ 时间内从 $1$ 号居民点到 $3$ 号居民点。 由 ChatGPT 4.1 翻译