Global Maximum Cut

Input

The first line of the input contains two integers, $n$ and $m$, representing the number of vertices and edges in the graph, respectively (2 \leq n \leq 1000, 1 \leq m \leq 30000). The following $m$ lines each describe an edge with three integers $a$, $b$, and $c$, indicating that there is an edge between vertices $a$ and $b$ with a cost of $c$ (0 \leq c \leq 10^9).

Output

Print the value of the global maximum cut.

Examples