Flubber Firefighting Network

Two years ago, you helped install the nation’s very first Flubber pipe network in your hometown – a huge success! Recently, enterprising citizens discovered that mixing Flubber with water can help extinguish fires. With fires running rampant, the city council has commissioned you to design a routing plan to send both Flubber and water through the same network of pipes from separate sources to the central Flubber Department (FD).

The network is an undirected graph. There is a Flubber factory (which is the source for Flubber) and a water source; both must send their liquid to the FD. Each bidirectional pipe (edge) has a capacity c (in liters/second) and may be used in only one direction for a given fluid flow so that if both fluids use the same pipe they must flow in the same direction. Moreover, if a pipe carries f liters/second of Flubber and w liters/second of water then they must satisfy the capacity constraint $$v \cdot f + w \le c,$$

where v (a positive integer) is the viscosity constant of Flubber (so that a pipe which can carry c liters/second of water can carry only c/v liters/second of pure Flubber).

The FD needs a balanced mixture. If F liters/second of Flubber and W liters/second of water reach the FD, the quality of the mixture is measured by $$F^{a} \cdot W^{1-a},$$

where a is a given constant between 0 and 1. Your task is to determine the maximum possible value of this expression and design a routing for the two fluids to achieve it.

Note: Although fluids may share pipes, if both are sent in the same direction through a pipe they mix and count toward the same capacity constraint. At every node (except the sources and the FD) the total inflow of each fluid must equal the total outflow. The nodes are equipped with special membranes and filters that allow you to separate and rearrange the flows arbitrarily.

inputFormat

The input begins with a line containing four numbers: n m v a, where

• n is the number of nodes,
• m is the number of pipes,
• v is the viscosity constant (an integer), and
• a is a real number between 0 and 1 used in the mixture quality formula.

The next line contains three integers: s_f s_w d, representing the node index of the Flubber factory (source for Flubber), the water source, and the FD (sink) respectively.

Then follow m lines. Each line contains three integers: u v c, indicating that there is an undirected pipe between nodes u and v with capacity c (in liters/second of water).

Important: In the network, both fluids share the same pipes. If a pipe carries f liters/second of Flubber and w liters/second of water, then the capacity constraint is
$$ v\cdot f + w \le c. $$

outputFormat

Output a single real number – the maximum possible value of the mixture quality, i.e. the maximum possible value of
$$ F^{a} \cdot W^{1-a} $$
achievable by routing the flows subject to the constraints. Your answer is accepted if its absolute or relative error does not exceed 10^-6.

sample

3 3 2 0.5
1 2 3
1 3 10
2 3 10
1 2 5

7.071067