Vor zwei Jahren hast du in deiner Heimatstadt geholfen, das allererste Flubber-Rohrnetz des Landes zu installieren, mit großem Erfolg. Umfragen zeigen, dass jeder seinen eigenen Flubber-Spender in der Küche liebt, und nun haben einige unternehmungslustige Bürger einen Verwendungszweck entdeckt. Offenbar hilft Flubber, mit Wasser vermischt, beim Feuerlöschen! Das kommt sehr gelegen, denn unkontrollierte Brände sind in letzter Zeit überraschend häufig.

Der Stadtrat möchte diese Eigenschaft nutzen und die Flubber-Wasser-Mischung an einer zentral gelegenen Station herstellen. Diese Station heißt Flubber Department (FD) und beschäftigt auch speziell ausgebildete Mitarbeiter, die zu Bränden fahren und das aufbereitete Flubber zur Eindämmung der Flammen verwenden.

Die Rohre liegen bereits überall in der Stadt. Ihre Anordnung ist gegeben, und du musst bestimmen, wie Flubber von der Fabrik und Wasser aus einer örtlichen Quelle durch die Rohre zum FD geleitet werden sollen.

Beide Flüssigkeiten fließen durch dasselbe Rohrnetz, möglicherweise sogar durch dasselbe Rohr. Alle Rohre sind in beide Richtungen nutzbar, aber Flubber und Wasser dürfen im selben Rohr nicht in entgegengesetzte Richtungen fließen. Fließen sie dort in dieselbe Richtung, vermischen sie sich zwangsläufig. Deshalb sind die Netzknoten mit speziellen Membranen und Filtern ausgestattet, mit denen du alle eingehenden Mischungen beliebig trennen und neu zusammensetzen kannst. Das Netz ist ein geschlossenes System: Für jede Flüssigkeit muss der gesamte Zufluss zu einem Knoten ihrem gesamten Abfluss entsprechen, außer an ihrer Quelle und am Ziel, dem FD.

Jedes Rohr hat eine Kapazität. Flubber ist etwas zähflüssig und besitzt die Viskosität $v$: Ein Rohr, das $v$ Liter Wasser pro Sekunde transportiert, schafft nur $1$ Liter Flubber pro Sekunde. Für Mischungen skaliert die Kapazität linear. Genauer: Ist $c$ die Wasserkapazität und sind $f,w$ die Flubber- und Wasserflussraten, alle in Litern pro Sekunde, so gilt $v \cdot f + w \le c$.

Deine Hauptsorge ist die Ausgewogenheit der Mischung am FD. Du möchtest möglichst viel Flüssigkeit insgesamt, aber auch genügend Wasser, denn unverdünntes Flubber ist leicht entzündlich, und genügend Flubber, denn ohne Flubber wäre es kaum ein „Flubber Department“! Du hast eine Formel für den „Wert“ der fertigen Mischung aufgestellt: $F^a \cdot W^{1-a}$. Dabei sind $F$ und $W$ die eintreffenden Flubber- und Wasserflussraten in Litern pro Sekunde, und $a$ ist eine gegebene Konstante zwischen $0$ und $1$.

Bestimme den maximal erreichbaren Wert von $F^a \cdot W^{1-a}$ und wie die beiden Flüssigkeiten dafür geleitet werden müssen.

Eingabe

Die erste Zeile enthält die Anzahl der Orte $n$ ($3 \le n \le 200$), die Anzahl der Rohre $p$ ($n-1 \le p \le \frac12 n(n-1)$) und die reellen Werte $v$ ($1 \le v \le 10$) und $a$ ($0.01 \le a \le 0.99$). Die Orte sind von $1$ bis $n$ nummeriert: $1$ ist die Flubber-Fabrik, $2$ die Wasserquelle und $3$ das FD. Die reellen Werte haben höchstens $10$ Nachkommastellen.

Die folgenden $p$ Zeilen beschreiben je ein Rohr. Jede enthält zwei ganze Zahlen $j,k$ ($1 \le j < k \le n$), die verbundenen Orte, sowie eine ganze Zahl $c$ ($1 \le c \le 10$), die Wasserkapazität in Litern pro Sekunde.

Keine zwei Rohre verbinden dasselbe Paar von Orten. Außerdem ist das Netz garantiert zusammenhängend.

Ausgabe

Gib zuerst für jedes Rohr in Eingabereihenfolge zwei Werte aus: die Flubber- und die Wasserflussrate, negativ bei Fluss von $k$ nach $j$, sodass $F^a \cdot W^{1-a}$ maximal wird. Gib anschließend diesen Maximalwert mit einem absoluten Fehler von höchstens $10^{-4}$ aus.

Bei mehreren Lösungen wird jede akzeptiert. Alle Bedingungen —keine entgegengesetzten Flussrichtungen der Flüssigkeiten im selben Rohr, Flusserhaltung, Rohrkapazitäten und Übereinstimmung zwischen konstruierter Lösung und angegebenem Wert— müssen bis auf einen absoluten Fehler von $10^{-4}$ erfüllt sein.

Beispiele

Eingabe 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

Ausgabe 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

Eingabe 2

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

Ausgabe 2

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