Hace dos años ayudaste a instalar en tu ciudad natal la primera red de tuberías de Flubber del país, con gran éxito. Las encuestas muestran que a todos les encanta tener su propio dispensador de Flubber en la cocina, y ahora unos ciudadanos emprendedores han descubierto un uso para él. ¡Al parecer, mezclado con agua, ayuda a apagar incendios! El descubrimiento llega muy a tiempo, pues últimamente los incendios descontrolados han sido sorprendentemente frecuentes.

El ayuntamiento quiere aprovechar esta propiedad creando la mezcla de Flubber y agua en una estación céntrica. Esta estación, llamada Flubber Department (FD), también contará con empleados especializados, formados para acudir a los incendios y usar su Flubber procesado para controlar las llamas.

Las tuberías ya están instaladas por toda la ciudad. Dado su trazado, debes determinar cómo enviar Flubber desde su fábrica y agua desde una fuente local, a través de las tuberías, hasta el FD.

Ambos líquidos circularán por la misma red, quizá incluso por la misma tubería. Todas las tuberías son bidireccionales, pero Flubber y agua no pueden circular en sentidos opuestos por una misma tubería. Si circulan en el mismo sentido por la misma tubería, inevitablemente se mezclarán. Por ello, los nodos tienen membranas y filtros especiales que permiten separar y reorganizar todas las mezclas entrantes como prefieras. La red es un sistema cerrado: el caudal total de cada líquido que entra en un nodo debe igualar al que sale, salvo en la fuente de ese líquido y en el destino, el FD.

Cada tubería tiene cierta capacidad. Flubber es algo viscoso, con valor de viscosidad $v$, por lo que una tubería que transporta $v$ litros de agua por segundo solo transporta $1$ litro de Flubber por segundo. La capacidad varía linealmente para mezclas. En concreto, si $c$ es la capacidad de agua y $f,w$ son los caudales de Flubber y agua (todos en litros por segundo), la restricción es $v \cdot f + w \le c$.

Tu principal preocupación es equilibrar la mezcla que llega al FD. Quieres la mayor cantidad total de líquido posible, pero también suficiente agua, porque Flubber sin diluir es muy inflamable, y suficiente Flubber, ¡porque sin él no sería gran cosa un «Flubber Department»! Has ideado una fórmula para medir el «valor» de la mezcla final: $F^a \cdot W^{1-a}$, donde $F$ es el caudal entrante de Flubber, $W$ el de agua, ambos en litros por segundo, y $a$ una constante dada entre $0$ y $1$.

Determina el máximo valor alcanzable de $F^a \cdot W^{1-a}$ y cómo encaminar Flubber y agua para lograrlo.

Entrada

La primera línea contiene el número de ubicaciones $n$ ($3 \le n \le 200$), el número de tuberías $p$ ($n-1 \le p \le \frac12 n(n-1)$) y los reales $v$ ($1 \le v \le 10$) y $a$ ($0.01 \le a \le 0.99$). Las ubicaciones se numeran de $1$ a $n$: $1$ es la fábrica de Flubber, $2$ la fuente de agua y $3$ el FD. Los reales tienen como máximo $10$ cifras decimales.

Las siguientes $p$ líneas describen una tubería cada una. Cada línea contiene dos enteros $j,k$ ($1 \le j < k \le n$), sus extremos, y un entero $c$ ($1 \le c \le 10$), su capacidad de agua en litros por segundo.

No hay dos tuberías entre el mismo par de ubicaciones. Además, se garantiza que la red es conexa.

Salida

Primero, para cada tubería, en el orden de entrada, imprime dos valores: su caudal de Flubber y su caudal de agua, negativos si el líquido fluye de $k$ a $j$, de modo que $F^a \cdot W^{1-a}$ sea máximo. Después imprime ese máximo con error absoluto no superior a $10^{-4}$.

Si hay varias soluciones, se acepta cualquiera. Todas las restricciones —no enviar los líquidos en sentidos opuestos por la misma tubería, conservación del flujo, capacidades y coherencia entre la solución construida y su valor declarado— deben cumplirse con error absoluto no superior a $10^{-4}$.

Ejemplos

Entrada 1

6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 3

Salida 1

0.000000000 1.360000000
0.000000000 1.000000000
0.000000000 -1.000000000
0.000000000 0.360000000
0.880000000 0.000000000
-0.880000000 -0.360000000
1.02037965897

Entrada 2

5 5 1.0 0.5
1 2 10
2 3 10
3 4 10
4 5 10
3 5 10

Salida 2

5 0
5 5
4.2 3.14159
4.2 3.14159
-4.2 -3.14159
5