eolymp
bolt
Try our new interface for solving problems
Problems

Maximum Flow A

Maximum Flow A

Time limit 1 second
Memory limit 128 MiB

The undirected graph without loops and multiple edges with n vertices is given (the vertices are numbered from 1 to n). For each edge we know its capacity. Find the value of the maximum flow from the vertex 1 to the vertex n. The current can flow along each edge in both directions.

Input data

Two numbers n and k~(2 \le n \le 100, 0 \le k \le n \cdot (n - 1) / 2) — the number of vertices and edges in a graph. Each of the next k lines contains three numbers a, b, c~(1 \le a, b \le n, 1 \le c \le 10^9) — the vertices, connected with an edge, and the capacity of this edge.

Output data

Print the maximum flow from the vertex 1 to the vertex n.

Examples

Input example #1
5 7
1 2 2
2 5 5
1 3 6
3 4 2
4 5 1
3 2 3
2 4 1
Output example #1
6
Source III International Summer School Programming in Sevastopol 2012