Implementation of Edmonds Karp algorithm that calculates maxFlow of graph.

Input:

For each test case, the first line contains the number of vertices (n) and the number of arcs (m). Then, there exist m lines, one for each arc (source vertex, ending vertex and arc weight, separated by a space). The nodes are numbered from 1 to n. The node 1 and node n should be in different sets. There are no more than 30 arcs and 15 nodes. The arc weights vary between 1 and 1 000 000.



Output:

The output is a single line for each case, with the corresponding minimum size cut.



Example:

Input:

7 11

1 2 3

1 4 3

2 3 4

3 1 3

3 4 1

3 5 2

4 6 6

4 5 2

5 2 1

5 7 1

6 7 9



Output:

5-Implementation of Edmonds Karp　algorithm that calculates maxFlow of graph.

Input:

For each test case, the first line contains the number of vertices (n) and the number of arcs (m). Then, there exist m lines, one for each arc (source vertex, ending vertex and arc weight, separated by a space). The nodes are numbered from 1 to n. The node 1 and node n should be in different sets. There are no more than 30 arcs and 15 nodes. The arc weights vary between 1 and 1 000 000.



Output:

The output is a single line for each case, with the corresponding minimum size cut.



Example:

Input:

7 11

1 2 3

1 4 3

2 3 4

3 1 3

3 4 1

3 5 2

4 6 6

4 5 2

5 2 1

5 7 1

6 7 9



Output:

5