Глобальный максимальный разрез

Дан неориентированный граф, каждое ребро которого имеет свою стоимость.

Найдите величину глобального максимального разреза.

Входные данные

В первой строке входного файла находится два числа n и m - число вершин и рёбер в графе соответственно (2 ≤ n ≤ 1000, 1 ≤ m ≤ 30000). Следующие m строк описывают рёбра и содержат по три числа a, b, c, ребро между a и b обладает пропускной способностью c (0 ≤ c ≤ 10^9).

Выходные данные

Выведите величину глобального максимального разреза.

Примеры