You are given an undirected graph. You want to compute the maximum flow from each vertex to every other vertex.

The graph is special. You can regard it as a convex polygon with points (vertices) and some line segments (edges) connecting them. The vertices are labeled from to in the clockwise order. The line segments can only intersect each other at the vertices.

Each edge has a capacity constraint.

Denote the maximum flow from to by . Output .

The first line contains two integers  and , representing the number of vertices and edges ().
Each of the next  lines contains three integers  denoting the two endpoints of an edge and its capacity ().
It is guaranteed there are no multiple edges and self-loops.
It is guaranteed that there is an edge between vertex  and vertex  for all .

Output the answer in one line.

6 8
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 1 100000
1 4 1000000
1 5 10000000

12343461