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

Задано неорієнтовний граф, кожне ребро якого має свою вартість.

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

Вхідні дані

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

Вихідні дані

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

Приклади