#216899. [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 buildings connected by sidewalks. The -th sidewalk connects buildings and , and is metres long. There is at most 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 and he can walk up to 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 and release a group of students at building . The students will spread out at metres per second along all sidewalks. The game of tag is over when Troy’s students reach Roger.

For each building , how long will the game of tag last?

The first line of input will consist of space-separated integers , , , (; ; ).

The next lines each contain integers, where the -th line contains integers , , (; ).

Output lines, where the -th line contains the duration of the game of tag in seconds if Troy releases a group of students at building . You must output the duration as a fraction in simplest terms.

Note that an integer is a divisor of an integer if there is no remainder when is divided by . An integer is a common divisor of integers and if is a divisor of both and . A fraction is in simplest terms if is positive, and and do not have a common divisor greater than .

样例输入 1

3 2 1 10
1 2 135
1 3 15

样例输出 1

15/1
5/3

样例输入 2

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

样例输出 2

4/1
4/1
5/1

Explanation of Output for Sample Input 1

:::align{center} :::

For , Roger should walk to building . After seconds, the students tag Roger at building and the game of tag is over.

For , Roger should walk towards building . After seconds, the students tag Roger at the sidewalk between buildings and and the game of tag is over. Notice that Roger walked metres and the students walked metres.

Explanation of Output for Sample Input 2

:::align{center} :::

For , Roger should walk to building .

For , Roger should walk to building .

For , Roger should walk to the centre of the sidewalk between buildings and .

The following table shows how the available marks are distributed: