Roger et Troy jouent à une partie de chat à l'Université de Waterloo. L'Université de Waterloo peut être représentée par $N$ bâtiments reliés par $M$ trottoirs. Le $i$-ième trottoir relie les bâtiments $a_i$ et $b_i$, et mesure $d_i$ mètres de long. Il y a au plus 1 trottoir entre n'importe quelle paire de bâtiments. Les trottoirs ne s'intersectent pas (c'est-à-dire que vous ne pouvez passer d'un trottoir à un autre qu'au niveau d'un bâtiment), et ils ne sont pas nécessairement situés sur un plan (en raison des ponts et des tunnels). En partant de n'importe quel bâtiment, il est possible d'atteindre n'importe quel autre bâtiment en marchant le long des trottoirs.

Roger commence la partie de chat au bâtiment 1 et il peut marcher jusqu'à $v_1$ mètres par seconde. Roger peut également attendre dans un bâtiment ou n'importe où sur un trottoir. Roger marchera de manière à maximiser la durée de la partie de chat.

Troy choisira un bâtiment $x$ et libérera un groupe d'étudiants au bâtiment $x$. Les étudiants se disperseront à $v_2$ mètres par seconde le long de tous les trottoirs. La partie de chat se termine lorsque les étudiants de Troy atteignent Roger.

Pour chaque bâtiment $x$, combien de temps durera la partie de chat ?

Entrée

La première ligne de l'entrée contiendra 4 entiers séparés par des espaces $N, M, v_1, v_2$ ($2 \le N \le 2\,000$; $N - 1 \le M \le 5\,000$; $1 \le v_1, v_2 \le 100$).

Les $M$ lignes suivantes contiennent chacune 3 entiers, où la $i$-ième ligne contient les entiers $a_i, b_i, d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).

Le tableau suivant montre comment les 25 points disponibles sont répartis :

Sortie

Affichez $N - 1$ lignes, où la $i$-ième ligne contient la durée de la partie de chat en secondes si Troy libère un groupe d'étudiants au bâtiment $i + 1$. Vous devez afficher la durée sous forme de fraction irréductible.

Notez qu'un entier $d$ est un diviseur d'un entier $q$ s'il n'y a pas de reste lorsque $q$ est divisé par $d$. Un entier $z$ est un diviseur commun des entiers $x$ et $y$ si $z$ est un diviseur à la fois de $x$ et de $y$. Une fraction $x/y$ est sous forme irréductible si $y$ est positif, et que $x$ et $y$ n'ont pas de diviseur commun supérieur à un.

Exemples

Entrée 1

3 2 1 10
1 2 135
1 3 15

Sortie 1

15/1
5/3

Remarque 1

Pour $x = 2$, Roger devrait marcher vers le bâtiment 3. Après 15 secondes, les étudiants attrapent Roger au bâtiment 3 et la partie de chat est terminée.

Pour $x = 3$, Roger devrait marcher vers le bâtiment 2. Après $5/3$ secondes, les étudiants attrapent Roger sur le trottoir entre les bâtiments 2 et 3 et la partie de chat est terminée. Remarquez que Roger a parcouru $1,666\dots$ mètres et que les étudiants ont parcouru $15 + 1,666\dots$ mètres.

Entrée 2

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

Sortie 2

4/1
4/1
5/1

Remarque 2

Pour $x = 2$, Roger devrait marcher vers le bâtiment 4.

Pour $x = 3$, Roger devrait marcher vers le bâtiment 4.

Pour $x = 4$, Roger devrait marcher vers le centre du trottoir entre les bâtiments 2 et 3.