P16901 [CCO 2026] Waterloo Tag

Roger and Troy are playing a game of tag at the University of Waterloo. The University of Waterloo can be represented as $N$ buildings connected by $M$ sidewalks. The $i$-th sidewalk connects buildings $a_i$ and $b_i$, and is $d_i$ metres long. There is at most $1$ sidewalk between any pair of buildings. The sidewalks do not intersect (i.e. you can only move from one sidewalk to another at a building), and they might not lie on a plane (due to bridges and tunnels). Starting from any building, it is possible to reach any other building by walking along the sidewalks. Roger starts the game of tag at building $1$ and he can walk up to $v_1$ metres per second. Roger can also wait at a building or wait anywhere on a sidewalk. Roger will walk in a way that maximizes the duration of the game of tag. Troy will pick a building $x$ and release a group of students at building $x$. The students will spread out at $v_2$ metres per second along all sidewalks. The game of tag is over when Troy’s students reach Roger. For each building $x$, how long will the game of tag last?

The first line of input will consist of $4$ space-separated integers $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$). The next $M$ lines each contain $3$ integers, where the $i$-th line contains integers $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10000$).

Output $N - 1$ lines, where the $i$-th line contains the duration of the game of tag in seconds if Troy releases a group of students at building $i + 1$. You must output the duration as a fraction in simplest terms. Note that an integer $d$ is a divisor of an integer $q$ if there is no remainder when $q$ is divided by $d$. An integer $z$ is a common divisor of integers $x$ and $y$ if $z$ is a divisor of both $x$ and $y$. A fraction $x/y$ is in simplest terms if $y$ is positive, and $x$ and $y$ do not have a common divisor greater than $1$.

**Explanation of Output for Sample Input 1** :::align{center}  ::: For $x = 2$, Roger should walk to building $3$. After $15$ seconds, the students tag Roger at building $3$ and the game of tag is over. For $x = 3$, Roger should walk towards building $2$. After $5/3$ seconds, the students tag Roger at the sidewalk between buildings $2$ and $3$ and the game of tag is over. Notice that Roger walked $1.666\ldots$ metres and the students walked $15 + 1.666\ldots$ metres. **Explanation of Output for Sample Input 2** :::align{center}  ::: For $x = 2$, Roger should walk to building $4$. For $x = 3$, Roger should walk to building $4$. For $x = 4$, Roger should walk to the centre of the sidewalk between buildings $2$ and $3$. The following table shows how the $25$ available marks are distributed: | Marks Awarded | Additional Constraints | |:-:|:-:| | $3$ marks | $N = 3$ and $M = 2$. | | $3$ marks | $N = 3$ and $M = 3$. | | $7$ marks | $v_1 = v_2 = 1$ and all sidewalks are $2$ metres long ($d_i = 2$). | | $7$ marks | $N \le 100$ and $M \le 200$. | | $5$ marks | None. |