Il y a deux ans, vous avez aidé à installer dans votre ville natale le tout premier réseau de conduites de Flubber du pays, avec grand succès. Les sondages montrent que chacun adore avoir son propre distributeur de Flubber dans sa cuisine, et des citoyens entreprenants viennent de lui découvrir une utilité. Apparemment, mélangé à l’eau, il aide à éteindre les incendies ! Cette découverte tombe à point nommé, car les incendies incontrôlables sont étonnamment fréquents ces derniers temps.

Le conseil municipal souhaite exploiter cette propriété en préparant le mélange Flubber/eau dans une station centrale. Cette station, appelée Flubber Department (FD), disposera aussi d’employés spécialisés, formés pour se rendre sur les lieux des incendies et utiliser le Flubber traité afin de maîtriser les flammes.

Les conduites sont déjà en place dans toute la ville. Leur tracé étant donné, vous devez déterminer comment acheminer le Flubber depuis l’usine et l’eau depuis une source locale, par ces conduites jusqu’au FD.

Le Flubber et l’eau circuleront dans le même réseau, voire dans la même conduite. Toutes les conduites sont bidirectionnelles, mais les deux liquides ne peuvent pas circuler en sens opposés dans une même conduite. S’ils y circulent dans le même sens, ils se mélangent inévitablement. Les nœuds sont donc équipés de membranes et de filtres spéciaux permettant de séparer et recomposer à volonté tous les mélanges entrants. Le réseau est un système fermé : pour chaque liquide, le débit total entrant dans un nœud doit égaler le débit sortant, sauf à sa source et à sa destination, le FD.

Chaque conduite a une capacité. Le Flubber, plutôt épais, a une viscosité $v$ : une conduite transportant $v$ litres d’eau par seconde ne peut transporter que $1$ litre de Flubber par seconde. La capacité varie linéairement pour les mélanges. Plus précisément, si $c$ est la capacité en eau et $f,w$ les débits de Flubber et d’eau, tous en litres par seconde, la contrainte est $v \cdot f + w \le c$.

Votre principale préoccupation est l’équilibre du mélange arrivant au FD. Vous souhaitez un volume total aussi grand que possible, mais aussi suffisamment d’eau, car le Flubber non dilué est très inflammable, et suffisamment de Flubber, car sans lui ce ne serait guère un « Flubber Department » ! Vous avez conçu une formule mesurant la « valeur » du mélange final : $F^a \cdot W^{1-a}$, où $F$ et $W$ sont les débits entrants de Flubber et d’eau en litres par seconde, et $a$ une constante donnée entre $0$ et $1$.

Déterminez la valeur maximale réalisable de $F^a \cdot W^{1-a}$ et comment acheminer les deux liquides pour l’atteindre.

Entrée

La première ligne contient le nombre de lieux $n$ ($3 \le n \le 200$), le nombre de conduites $p$ ($n-1 \le p \le \frac12 n(n-1)$), ainsi que les réels $v$ ($1 \le v \le 10$) et $a$ ($0.01 \le a \le 0.99$). Les lieux sont numérotés de $1$ à $n$ : $1$ est l’usine de Flubber, $2$ la source d’eau et $3$ le FD. Les réels ont au plus $10$ chiffres après la virgule.

Les $p$ lignes suivantes décrivent chacune une conduite. Chaque ligne contient deux entiers $j,k$ ($1 \le j < k \le n$), les lieux reliés, et un entier $c$ ($1 \le c \le 10$), sa capacité en eau en litres par seconde.

Deux conduites ne relient jamais la même paire de lieux. De plus, le réseau est garanti connexe.

Sortie

Affichez d’abord, pour chaque conduite dans l’ordre d’entrée, deux valeurs : son débit de Flubber et son débit d’eau, négatifs si le liquide va de $k$ vers $j$, de façon à maximiser $F^a \cdot W^{1-a}$. Affichez ensuite ce maximum avec une erreur absolue d’au plus $10^{-4}$.

S’il existe plusieurs solutions, chacune est acceptée. Toutes les contraintes —absence de circulation des liquides en sens opposés dans une même conduite, conservation des débits, capacités et cohérence entre la solution construite et sa valeur annoncée— doivent être respectées à une erreur absolue de $10^{-4}$ près.

Exemples

Entrée 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

Sortie 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

Entrée 2

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

Sortie 2

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