P16901 [CCO 2026] Waterloo Tag

罗杰（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$ 的公约数。

**样例输入 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$ 分的分配情况： | 分值 | 额外限制 | |:-:|:-:| | $3$ 分 | $N = 3$ 且 $M = 2$。 | | $3$ 分 | $N = 3$ 且 $M = 3$。 | | $7$ 分 | $v_1 = v_2 = 1$ 且所有人行道长度均为 $2$ 米（$d_i = 2$）。 | | $7$ 分 | $N \le 100$ 且 $M \le 200$。 | | $5$ 分 | 无。 | 翻译由 DeepSeek V4 Pro 完成