Special Flow

Time Limit: 1 Second
Memory Limit: 32768 KB
Special Judge

There are n junctions numbered from 1 to *n*, connected by **undirected** pipes,
in which water can flow through. Junction 1 is the source, junction *n* is the
sink. Pipes have capacities, restricting the maximal velocity that water can
move through. There will be no water leak, so for every junction (except the
source and sink), the amount of water flowing into the junction is equal to
the amount of water flowing out of it.

Your task is to find the maximal volume of water that can flow from junction 1
to junction *n*, during one unit time. Isn't it the traditional max-flow problem?
Well, not exactly. There is an additional restriction in this problem: for an arbitrary
pair of junctions *u* and *v*, there is a constant S(*u*,*v*) such that, in **every** path from *u*
and *v*, the **sum of water velocity** on the arcs along the path is always S(*u*,*v*). We calculate
the sum in a way such that if the water flows against direction of the path from *u* to *v*,
its velocity is negated. Note that, for two different pairs (*u*_{1},*v*_{1}) and (*u*_{2},*v*_{2}), S(*u*,*v*)
may be different from S(*u*_{2},*v*_{2}).

The picture above shows an example pipe network. Capacities of the pipes
are shown in the left, while the actual water velocity and flowing directions
are shown in the right. You can examine, for example, S(2,4) = 2.8, S(3,1)=-2, S(1,4)=4.4.

**Input**

There will be at most 30 test cases. Each case begins with two integers n and m
(2 <= *n* <= 100, 1 <= *m* <= 5000), the number of junctions and pipes. The next *m* lines contain
the description of pipes. Each pipe is represented by three integers *a*, *b* and *c*, where *a* and
*b* are the numbers of two **different** junctions connected by the pipe, and *c* is the maximal possible
water velocity in that pipe (0 <= *c* <= 10000). The input ends with *n* = *m* = 0. There can be multiple
pipes between a given pair of junctions.

**Output**

For each test case, print the maximum volume as a floating point number (in any format you like).
This number should match the exact result with the maximal absolute difference of 0.0001.

**Sample Input**

4 6
1 3 2
1 2 3
1 2 2
2 4 5
2 3 2
3 4 5
0 0

**Sample Output**

5.2

Author:

**LIU, Rujia**
Source:

**The 34th ACM-ICPC Asia Regional 2009 Ningbo Site NIT Cup National Invitation Contest**
Submit
Status