Electrical grids P17957

The electrical grids of the United States and Italy have recently shown deficiencies. To prevent them, Catalan engineers are faced with the following problem.

Electricity must be sent, through several wires, from a power plant where it is produced to a city where it is consumed. Each wire is defined by some capacity and by two vertices that join them to other wires: an input vertex where electricity enters the wire and an output vertex where electricity leaves the wire. Every vertex can distribute electricity as it likes, as long as capacity restrictions are not violated and the amount of electricity that enters the vertex equals the amount of electricity that leaves it.

Which is the greatest amount of electricity shippable from the power plant to the city?

Input

Input consists of several cases. Each case begins with the number of vertices $2 \le n \le 5000$ and the number of wires $0 \le m \le 10n$. Follow $m$ trios of natural numbers $u$, $v$ and $c$, to indicate a wire from vertex $u$ to vertex $v$ (where $u \ne v$) with capacity $c$. Vertices are labeled from 0 to $n-1$. Vertex 0 corresponds to the power plant and vertex $n-1$ to the city. Assume $1 \le c \le 5000$ and that for every two vertices $u$ and $v$ there is at most one wire from $u$ to $v$.

Output

For every case, print the maximum amount of electricity that can be sent from the power plant to the city.