One of 's research interests is the maximum flow problem.
A directed graph with vertices is if the following condition is satisfied:

•   is the union of vertex-independent simple paths from vertex to vertex n of the same length.

A set of paths is vertex-independent if they do not have any internal vertex in common.
A vertex in a path is called internal if it is not an endpoint of that path.
A path is simple if its vertices are distinct.
Let be a graph with vertices and edges. Each edge has a non-negative integral capacity. You are allowed to perform the following operation any (including ) times to make the maximum flow from vertex to vertex as large as possible:
Let be an edge with positive capacity. Reduce the capacity of by and increase the capacity of another edge by .
wants to know what is the minimum number of operations to achieve it?

The first line contains two integers  and  ().
Each of the next  lines contains three integers  and , denoting an edge from  to  with capacity  (, ).
It's guaranteed that the input is a universe graph without multiple edges and self-loops.

Output a single integer --- the minimum number of operations.

4 3
1 2 1
2 3 2
3 4 3

1

4 4
1 2 1
1 3 1
2 4 2
3 4 2

1