Uniform flow
In a network of nodes connected by pipes, water flows through the system. Each pipe has a known maximum flow speed. Water flows such that, for every node (except the source and the sink), the amount of water entering equals the amount leaving in each unit of time. Additionally, for any pair of nodes, including the source and the sink, the sum of the flow speeds along any path connecting them remains constant. If a pipe is traversed against the direction of flow, its contribution to the sum is negative.
Your task is to determine the maximum flow of water from the source to the sink per unit of time.
The pipes are bidirectional, allowing water to flow in either direction. Multiple pipes may exist between any pair of nodes.
Input
The first line contains an integer N, representing the number of nodes in the system (2 ≤ N ≤ 100). The source is node 1, and the sink is node N. The second line contains an integer M (1 ≤ M ≤ 5000), indicating the number of pipes. The following M lines describe each pipe with three integers Ai, Bi, Ci, where Ai and Bi are the nodes connected by the pipe, and Ci (0 ≤ Ci ≤ 10000) is the maximum flow speed through the pipe.
Output
Print the maximum flow of water from the source to the sink per unit of time, with a precision of 10^{-3}.