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.
Two numbers n and k (2≤n≤100,0≤k≤n⋅(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≤a,b≤n,1≤c≤109) — the vertices, connected with an edge, and the capacity of this edge.
Print the maximum flow from the vertex 1 to the vertex n.