Global Maximum Cut

Given an undirected graph where each edge has an associated cost, your task is to determine the value of the 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 ≤ n ≤ 1000, 1 ≤ m ≤ 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 ≤ c ≤ 10^9).

Output

Print the value of the global maximum cut.

Examples