Roger y Troy están jugando a las traes en la Universidad de Waterloo. La Universidad de Waterloo puede representarse como $N$ edificios conectados por $M$ aceras. La $i$-ésima acera conecta los edificios $a_i$ y $b_i$, y tiene una longitud de $d_i$ metros. Existe como máximo 1 acera entre cualquier par de edificios. Las aceras no se cruzan (es decir, solo se puede pasar de una acera a otra en un edificio) y podrían no estar en un mismo plano (debido a puentes y túneles). Partiendo de cualquier edificio, es posible llegar a cualquier otro edificio caminando por las aceras.

Roger comienza el juego de las traes en el edificio 1 y puede caminar hasta $v_1$ metros por segundo. Roger también puede esperar en un edificio o en cualquier lugar de una acera. Roger caminará de una manera que maximice la duración del juego de las traes.

Troy elegirá un edificio $x$ y liberará a un grupo de estudiantes en el edificio $x$. Los estudiantes se dispersarán a $v_2$ metros por segundo a lo largo de todas las aceras. El juego de las traes termina cuando los estudiantes de Troy alcanzan a Roger.

Para cada edificio $x$, ¿cuánto durará el juego de las traes?

Entrada

La primera línea de la entrada consistirá en 4 enteros separados por espacios $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$).

Las siguientes $M$ líneas contienen cada una 3 enteros, donde la $i$-ésima línea contiene los enteros $a_i, b_i, d_i$ ($1 \le a_i < b_i \le N$; $1 \le d_i \le 10\,000$).

La siguiente tabla muestra cómo se distribuyen los 25 puntos disponibles:

Salida

Imprima $N - 1$ líneas, donde la $i$-ésima línea contiene la duración del juego de las traes en segundos si Troy libera a un grupo de estudiantes en el edificio $i + 1$. Debe imprimir la duración como una fracción en términos simples.

Tenga en cuenta que un entero $d$ es divisor de un entero $q$ si no hay residuo cuando $q$ se divide por $d$. Un entero $z$ es un divisor común de los enteros $x$ e $y$ si $z$ es divisor tanto de $x$ como de $y$. Una fracción $x/y$ está en términos simples si $y$ es positivo, y $x$ e $y$ no tienen un divisor común mayor que uno.

Ejemplos

Entrada 1

3 2 1 10
1 2 135
1 3 15

Salida 1

15/1
5/3

Nota 1

Para $x = 2$, Roger debería caminar hacia el edificio 3. Después de 15 segundos, los estudiantes atrapan a Roger en el edificio 3 y el juego termina.

Para $x = 3$, Roger debería caminar hacia el edificio 2. Después de $5/3$ segundos, los estudiantes atrapan a Roger en la acera entre los edificios 2 y 3 y el juego termina. Observe que Roger caminó $1.666\dots$ metros y los estudiantes caminaron $15 + 1.666\dots$ metros.

Entrada 2

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

Salida 2

4/1
4/1
5/1

Nota 2

Para $x = 2$, Roger debería caminar hacia el edificio 4.

Para $x = 3$, Roger debería caminar hacia el edificio 4.

Para $x = 4$, Roger debería caminar hacia el centro de la acera entre los edificios 2 y 3.