Há dois anos, ajudaste a instalar na tua terra a primeira rede de tubagens de Flubber do país, com grande sucesso. As sondagens mostram que todos adoram ter o seu dispensador de Flubber na cozinha, e agora alguns cidadãos empreendedores descobriram uma utilidade para ele. Pelos vistos, misturado com água, pode ajudar a apagar incêndios! A descoberta é oportuna, pois ultimamente têm sido surpreendentemente frequentes os incêndios descontrolados.

A câmara municipal quer aproveitar esta propriedade, criando a mistura de Flubber e água numa estação central. Esta estação, chamada Flubber Department (FD), terá também funcionários especializados, treinados para se deslocarem aos incêndios e usarem o Flubber processado para controlar as chamas.

As tubagens já estão instaladas por toda a cidade. Dado o seu traçado, deves determinar como encaminhar Flubber da fábrica e água de uma fonte local pelas tubagens até ao FD.

Ambos os líquidos percorrem a mesma rede, talvez até o mesmo tubo. Todos os tubos são bidirecionais, mas Flubber e água não podem circular em sentidos opostos no mesmo tubo. Se ambos circularem no mesmo sentido no mesmo tubo, misturam-se inevitavelmente. Por isso, os nós dispõem de membranas e filtros especiais que permitem separar e reorganizar todas as misturas recebidas como entenderes. A rede é um sistema fechado: o caudal total de cada líquido que entra num nó deve igualar o que sai, exceto na fonte desse líquido e no destino, o FD.

Cada tubo tem uma capacidade. Flubber é algo espesso, com viscosidade $v$, pelo que um tubo que transporta $v$ litros de água por segundo só transporta $1$ litro de Flubber por segundo. A capacidade varia linearmente para misturas dos dois. Precisamente, se $c$ é a capacidade de água e $f,w$ são os caudais de Flubber e água, todos em litros por segundo, a restrição é $v \cdot f + w \le c$.

A preocupação principal é equilibrar a mistura que chega ao FD. Queres a maior quantidade total possível, mas também água suficiente, porque Flubber não diluído é muito inflamável, e Flubber suficiente, porque sem ele não haveria grande «Flubber Department»! Criaste uma fórmula para medir o «valor» da mistura final: $F^a \cdot W^{1-a}$, em que $F$ é o caudal recebido de Flubber, $W$ o de água, ambos em litros por segundo, e $a$ uma constante dada entre $0$ e $1$.

Determina o valor máximo atingível de $F^a \cdot W^{1-a}$ e como encaminhar Flubber e água para o atingir.

Entrada

A primeira linha contém o número de locais $n$ ($3 \le n \le 200$), o número de tubos $p$ ($n-1 \le p \le \frac12 n(n-1)$) e os reais $v$ ($1 \le v \le 10$) e $a$ ($0.01 \le a \le 0.99$). Os locais são numerados de $1$ a $n$: $1$ é a fábrica de Flubber, $2$ a fonte de água e $3$ o FD. Os reais têm, no máximo, $10$ casas decimais.

As $p$ linhas seguintes descrevem um tubo cada uma. Cada linha contém dois inteiros $j,k$ ($1 \le j < k \le n$), os locais ligados, e um inteiro $c$ ($1 \le c \le 10$), a capacidade de água em litros por segundo.

Não há dois tubos a ligar o mesmo par de locais. Além disso, garante-se que a rede é conexa.

Saída

Primeiro, para cada tubo, pela ordem da entrada, apresenta dois valores: o caudal de Flubber e o de água, negativos se o líquido circular de $k$ para $j$, de modo a maximizar $F^a \cdot W^{1-a}$. Depois apresenta esse máximo com erro absoluto não superior a $10^{-4}$.

Se houver várias soluções, qualquer uma será aceite. Todas as restrições —não enviar os líquidos em sentidos opostos no mesmo tubo, conservação do caudal, capacidades e consistência entre a solução construída e o valor declarado— devem ser satisfeitas com erro absoluto não superior a $10^{-4}$.

Exemplos

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

Saída 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

Saída 2

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