Roger i Troy grają w berka na Uniwersytecie Waterloo. Uniwersytet Waterloo można przedstawić jako $N$ budynków połączonych $M$ chodnikami. $i$-ty chodnik łączy budynki $a_i$ oraz $b_i$ i ma długość $d_i$ metrów. Pomiędzy dowolną parą budynków istnieje co najwyżej jeden chodnik. Chodniki nie przecinają się (tzn. z jednego chodnika na drugi można przejść tylko w budynku) i mogą nie leżeć na jednej płaszczyźnie (z powodu mostów i tuneli). Z dowolnego budynku można dotrzeć do każdego innego budynku, poruszając się wzdłuż chodników.

Roger rozpoczyna grę w berka w budynku 1 i może poruszać się z prędkością do $v_1$ metrów na sekundę. Roger może również czekać w budynku lub w dowolnym miejscu na chodniku. Roger będzie poruszał się w taki sposób, aby zmaksymalizować czas trwania gry w berka.

Troy wybierze budynek $x$ i wypuści grupę studentów z budynku $x$. Studenci będą rozprzestrzeniać się z prędkością $v_2$ metrów na sekundę wzdłuż wszystkich chodników. Gra w berka kończy się, gdy studenci Troya dotrą do Rogera.

Dla każdego budynku $x$, jak długo potrwa gra w berka?

Wejście

Pierwsza linia wejścia zawiera 4 liczby całkowite oddzielone spacjami: $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$).

Kolejne $M$ linii zawiera po 3 liczby całkowite, gdzie $i$-ta linia zawiera liczby $a_i, b_i, d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).

Poniższa tabela przedstawia podział 25 dostępnych punktów:

Wyjście

Wypisz $N-1$ linii, gdzie $i$-ta linia zawiera czas trwania gry w berka w sekundach, jeśli Troy wypuści grupę studentów z budynku $i+1$. Czas należy podać w postaci ułamka nieskracalnego.

Zauważ, że liczba całkowita $d$ jest dzielnikiem liczby całkowitej $q$, jeśli przy dzieleniu $q$ przez $d$ nie ma reszty. Liczba całkowita $z$ jest wspólnym dzielnikiem liczb całkowitych $x$ oraz $y$, jeśli $z$ jest dzielnikiem zarówno $x$, jak i $y$. Ułamek $x/y$ jest w postaci nieskracalnej, jeśli $y$ jest dodatnie, a $x$ oraz $y$ nie mają wspólnego dzielnika większego niż jeden.

Przykład

Wejście 1

3 2 1 10
1 2 135
1 3 15

Wyjście 1

15/1
5/3

Uwagi 1

Dla $x = 2$, Roger powinien udać się do budynku 3. Po 15 sekundach studenci łapią Rogera w budynku 3 i gra kończy się.

Dla $x = 3$, Roger powinien udać się w stronę budynku 2. Po $5/3$ sekundy studenci łapią Rogera na chodniku między budynkami 2 i 3 i gra kończy się. Zauważ, że Roger przeszedł $1.666\dots$ metra, a studenci przeszli $15 + 1.666\dots$ metra.

Wejście 2

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

Wyjście 2

4/1
4/1
5/1

Uwagi 2

Dla $x = 2$, Roger powinien udać się do budynku 4.

Dla $x = 3$, Roger powinien udać się do budynku 4.

Dla $x = 4$, Roger powinien udać się do środka chodnika między budynkami 2 i 3.