400397: GYM100162 D Heating System

The house heating system consists of n nodes and m bidirectional pipes connecting pairs of nodes. The system is designed so that the hot water is circulating through the pipes and the amount of water coming to each node (in a unit of time) is equal to the amount of water leaving the node. The only exceptions are two special nodes: source (has outgoing flow) and sink (has incoming flow). All other nodes satisfy the restriction that the amount of flow into a node equals the amount of flow out of it.

Each pipe is described by two properties: capacity and friction coefficient. The capacity of the i-th pipe is denoted as c_i and stands for the maximal amount of water that can pass through it in a unit of time. Water can move in any of two directions in a pipe. The friction coefficient of the i-th pipe is denoted as p_i. The friction in the i-th pipe depends on p_i and the current flow f_i through it, the friction value is equal to p_i·f_i².

It is known that water passes the heating system in such a way that the total flow is maximal. It means that the amount of the water passing through the system in a unit of time is maximal. Among all the ways satisfying the first property, the flow passes through the system in such a way that the sum of all frictions is minimal.

Write the program which finds such maximal flow that the total friction is minimal.

The input contains several test cases. Each test case starts with a line containing two positive integers n and m (2 ≤ n ≤ 50, 1 ≤ m ≤ 100) as described above. The following m lines contain four integer numbers x_i, y_i, c_i and p_i (1 ≤ x_i, y_i ≤ n; x_i ≠ y_i; 1 ≤ c_i, p_i ≤ 50), where x_i and y_i are the numbers of the nodes connected by the i-th pipe, c_i and p_i are the capacity and friction coefficient of the i-th pipe. There is no more than one pipe between any pair of nodes. The nodes are numbered from 1 to n.

The first node is a source, the last node is a sink. It is also guaranteed that the sink is reachable from the source by the pipes.

For each test case, display the case number, the maximal flow value and the minimal total friction. Display the flow and the friction with at least 3 digits after the decimal point. Print the flows f₁, f₂, ..., f_m through the pipes 1, 2, ..., m. Positive f_i stands for the flow direction from the x_i to y_i, while a negative value stands for the opposite direction. Display each f_i in the output with at least 9 digits after the decimal point.

5 5
2 1 1 1
2 3 1 1
1 4 1 1
4 3 1 1
3 5 1 1
3 1
1 3 13 17

Case 1: 1.0000000000 2.0000000000
-0.5000000000 0.5000000000 0.5000000000 0.5000000000 1.0000000000 
Case 2: 13.0000000000 2873.0000000000
13.0000000000