Uniform flow#191
In a system of nodes connected by pipes, water can flow through the network. Each pipe has a known maximum possible flow rate. Water flows through the pipes so that, for every node (except the source and the sink), the total amount of water entering the node equals the total amount leaving it in each unit of time. Additionally, for any pair of nodes (including the source and the sink), the sum of the flow rates along any path connecting them is constant for that node pair. If a pipe is traversed in the path opposite to its flow direction, its contribution to the sum is taken with a minus sign.
Your task is to determine the maximum amount of water that can flow from the source to the sink per unit of time.
The pipes are bidirectional, meaning water can flow in either direction. There may be multiple pipes between any pair of nodes.
The first line contains a natural number (2 \leq N \leq 100) — the number of nodes in the system. The source has number , and the sink has number .
The second line contains a natural number (1 \leq M \leq 5000) — the number of pipes in the system.
The following lines describe the pipes. Each pipe is specified by three integers A_i, B_i, C_i, where A_i and B_i are the numbers of the nodes connected by the pipe, and C_i (0 \leq C_i \leq 10000) is the maximum possible flow rate through this pipe.
Print the maximum amount of water that can flow from the source to the sink per unit of time. Print the answer with precision 10^{-3}.
Example 1