题目描述

罗杰（Roger）和特洛伊（Troy）在滑铁卢大学玩捉人游戏。滑铁卢大学可以用 $N$ 栋建筑和 $M$ 条人行道表示。第 $i$ 条人行道连接建筑 $a_i$ 和 $b_i$，长度为 $d_i$ 米。任意两栋建筑之间最多有 $1$ 条人行道。人行道不会相交（即你只能通过建筑从一条人行道走到另一条），并且由于桥梁和隧道，它们可能不位于同一平面内。从任意建筑出发，沿着人行道都可以到达其他任意建筑。

罗杰从建筑 $1$ 开始游戏，他每秒最多可以走 $v_1$ 米。罗杰可以在建筑处等待，也可以在人行道上任意位置等待。罗杰会采取能够最大化游戏持续时间的行走策略。

特洛伊会选择一个建筑 $x$，并在建筑 $x$ 释放一批学生。学生们会以每秒 $v_2$ 米的速度沿所有人行道扩散。当特洛伊的学生们抓到罗杰时，游戏结束。

对于每个建筑 $x$，游戏会持续多长时间？

输入格式

输入的第一行包含 $4$ 个空格分隔的整数 $N$, $M$, $v_1$, $v_2$ ($2 \le N \le 2000$；$N - 1 \le M \le 5000$；$1 \le v_1, v_2 \le 100$)。

接下来的 $M$ 行每行包含 $3$ 个整数，其中第 $i$ 行包含整数 $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le N$；$1 \le d_i \le 10000$)。

输出格式

输出 $N - 1$ 行，其中第 $i$ 行包含当特洛伊在建筑 $i + 1$ 释放学生时游戏的持续时间（以秒为单位）。你必须以最简分数的形式输出持续时间。

注意，如果整数 $q$ 除以整数 $d$ 没有余数，则称 $d$ 是 $q$ 的约数。如果整数 $z$ 同时是 $x$ 和 $y$ 的约数，则称 $z$ 为 $x$ 和 $y$ 的公约数。分数 $x/y$ 被称为最简分数，当且仅当 $y$ 为正数，且 $x$ 与 $y$ 没有大于 $1$ 的公约数。

3 2 1 10
1 2 135
1 3 15

15/1
5/3

4 4 1 1
1 2 2
1 3 2
2 3 2
1 4 2

4/1
4/1
5/1

提示

样例输入 1 的输出解释

:::align{center} :::

对于 $x = 2$，罗杰应该走向建筑 $3$。$15$ 秒后，学生们在建筑 $3$ 抓到罗杰，游戏结束。

对于 $x = 3$，罗杰应该走向建筑 $2$。$5/3$ 秒后，学生们在建筑 $2$ 和 $3$ 之间的人行道上抓到罗杰，游戏结束。注意罗杰走了 $1.666\ldots$ 米，而学生们走了 $15 + 1.666\ldots$ 米。

样例输入 2 的输出解释

:::align{center} :::

对于 $x = 2$，罗杰应该走向建筑 $4$。

对于 $x = 3$，罗杰应该走向建筑 $4$。

对于 $x = 4$，罗杰应该走向建筑 $2$ 和 $3$ 之间人行道的中心点。

以下表格展示了可获得的 $25$ 分的分配情况：

翻译由 DeepSeek V4 Pro 完成