Flubber and Water Pipe Network

Two years ago you helped install the country's first Flubber pipe network in your hometown. Every kitchen now has its own Flubber tap. Someone recently found out that Flubber mixed with water puts out fires, and fires have been frequent lately, so the discovery is useful.

The city council wants to prepare the Flubber and water mixture at one central station in the middle of the city, the Flubber Department (FD). Trained staff at the FD carry the processed Flubber to the fires.

The pipes are already in place. Given the layout, you decide how to send Flubber from the Flubber factory and water from the local source through the pipes to the FD.

Both liquids flow through the same network, sometimes through the same pipe. Every pipe is bidirectional, but Flubber and water cannot move in opposite directions through one pipe. If both liquids move in the same direction through one pipe they always mix, so every location has membranes and filters that let you separate and rearrange any incoming mixture as you like. The network is a closed system, so at every location other than the source of a liquid and the FD, the rate of that liquid coming in equals the rate going out.

Each pipe has a capacity. Flubber is sluggish and has viscosity $v$, so a pipe that carries $v$ liters per second of water carries only 1 liter per second of Flubber. For mixtures the capacity changes linearly. If $c$ is the water capacity of a pipe and $f$ and $w$ are the rates of Flubber and water through it in liters per second, then $v \cdot f + w \le c$ must hold.

The mixture reaching the FD needs enough water, because undiluted Flubber catches fire easily, and enough Flubber, because a Flubber Department without Flubber is pointless. The value of the final mixture is $F^a W^{1-a}$, where $F$ is the rate of Flubber arriving at the FD, $W$ is the rate of water arriving there, and $a$ is a given constant between 0 and 1.

Find the maximum value of $F^a W^{1-a}$ that can be achieved.

The first line contains the number of locations $n$ ($3 \le n \le 200$), the number of pipes $p$ ($n - 1 \le p \le n(n-1)/2$), and the real numbers $v$ ($1 \le v \le 10$) and $a$ ($0.01 \le a \le 0.99$). Locations are numbered from 1 to $n$. Location 1 is the Flubber factory, location 2 is the water source, and location 3 is the FD. The real numbers have at most 10 digits after the decimal point.

Each of the next $p$ lines describes one pipe. Each line contains two integers $j$ and $k$ ($1 \le j < k \le n$), the locations the pipe connects, and an integer $c$ ($1 \le c \le 10$), the water capacity of the pipe in liters per second.

No two pipes connect the same pair of locations, and the network is connected.

Print the maximum achievable value of $F^a W^{1-a}$ on one line, rounded to exactly six digits after the decimal point. Do not print the flow through each pipe.