ICPC 2017 · Problem J · Son of Pipe Stream

Time limit: 5 seconds

Two years ago, you helped install the nation’s very first Flubber pipe network in your hometown, to great success. Polls show that everyone loves having their own Flubber dispenser in their kitchen, and now a few enterprising citizens have discovered a use for it. Apparently Flubber, when mixed with water, can help extinguish fires! This is a very timely discovery, as out-of-control fires have lately been surprisingly common.

Your hometown’s city council would like to make use of this property of Flubber by creating the Flubber/wa- ter mixture at a centrally located station. This station, which is called the Flubber Department (FD) will also have specialized employees trained to travel to the locations of fires and make use of their processed Flubber to control the blazes.

The pipes are already in place all around the city. You are given a layout of the pipes, and must determine how to route Flubber from the Flubber factory and water from a local source through the pipes to the FD.

Note that both Flubber and water will be flowing through the same network of pipes, perhaps even the same pipe. All pipes are bidirectional, but Flubber and water cannot move in opposite directions through the same pipe. Furthermore, if both liquids are sent in the same direction through the same pipe, they will inevitably mix. Therefore the nodes in the network have been equipped with special membranes and filters that enable you to separate and reorganize all incoming mixtures as you see fit. The network is a closed system, so the total rate of each fluid going into a node must equal the total rate of that fluid going out, except at the source of that fluid and the destination (the FD).

Each pipe has a certain capacity. Flubber, being somewhat sluggish, has a viscosity value $v$, so a pipe that can transport $v$ liters/second of water can transport only $1$ liter/second of Flubber. The pipe’s capacity scales linearly for mixtures of the two. To be precise, if $c$ denotes the water capacity of the pipe and $f$ and $w$ are the rates of Flubber and water moving through the pipe (all measured in liters/second), then the capacity constraint is given by the inequality $v\cdot f +w \le c$.

Your main concern is balancing the mixture that reaches the FD. You would like as much total liquid as possible, but you also need a sufficient amount of water – because undiluted Flubber is highly flammable

• and a sufficient amount of Flubber – because it would not be much of a “Flubber Department” without

Flubber! You have come up with a formula to measure the “value” of the final mixture: $F ^{a}\cdot W ^{1- a}$, where $F$ is the rate of incoming Flubber in liters/second, $W$ is the rate of incoming water in liters/second, and $a$ is a given constant between $0$ and $1$.

Determine the maximum value of $F ^{a}\cdot W ^{1- a}$ that can be achieved and how to route the Flubber and water to achieve it.

Input

The input starts with a line containing the number of locations $n$ ($3 \le n \le 200$), the number of pipes $p$ ($n- 1 \le p \le ^{1}$ $_{2}n(n- 1)$), and the real values $v$ ($1 \le v \le 10$) and $a$ ($0.01 \le a \le 0.99$). Locations are numbered from $1$ to $n$; $1$ is the Flubber factory, $2$ is the water source, and $3$ is the FD. The real values have at most $10$ digits after the decimal point.

ACM-ICPC World Finals 2017 Problem J: Son of Pipe Stream The following $p$ lines each describe one pipe. Each line contains two integers $j$ and $k$ ($1 \le j < k \le n$), giving the locations connected by the pipe, and an integer $c$ ($1 \le c \le 10$), giving the water capacity of the pipe in liters/second.

No two pipes connect the same pair of locations. Furthermore, it is guaranteed that the network is connected.

Output

First, for each pipe (in the order given in the input), display two values: the rate of Flubber moving through it, and the rate of water moving through it (negative if the liquid is moving from $k$ to $j$), such that $F ^{a}\cdot W ^{1- a}$ is maximized. Then display that maximum value accurate to within an absolute error of $10^{- 4}$.

If there are multiple solutions, any one will be accepted. All constraints (not sending Flubber and water in opposite directions along the same pipe, flow conservation, pipe capacities, and consistency between the constructed solution and its claimed value) must be satisfied within an absolute error of $10^{- 4}$.

Sample Input 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

Sample Output 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

Sample Input 2

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

Sample Output 2

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

ACM-ICPC World Finals 2017 Problem J: Son of Pipe Stream