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

Вхідні дані

У першому рядку вхідного файлу знаходиться два числа $n$ та $m$ — число вершин та ребер у графі відповідно (2 \leq n \leq 1000, 1 \leq m \leq 30000). Наступні $m$ рядків описують ребра і містять по три числа $a$, $b$, $c$ — ребро між $a$ та $b$ має вагу $c$ (0 \leq c \leq 10^9).

Вихідні дані

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

Приклади