eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Максимальний потік A

Максимальний потік A

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Дано неорієнтований граф без петель та кратних ребер з n вершин (вершини нумеруються від 1 до n). Для кожного ребра відома його пропускна спроможність. Знайдіть величину максимального потоку з вершини 1 до вершини n. По кожному ребру потік може текти у довільну сторону.

Вхідні дані

Два числа n та k~(2 \le n \le 100, 0 \le k \le n \cdot (n - 1) / 2) — кількість вершин та ребер у графі. Далі йдуть k рядків по три числа в кожному — a, b, c~(1 \le a, b \le n, 1 \le c \le 10^9) — номери вершин, сполучених ребром, та пропускна спроможність ребра.

Вихідні дані

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

Приклад

Вхідні дані #1
5 7
1 2 2
2 5 5
1 3 6
3 4 2
4 5 1
3 2 3
2 4 1
Вихідні дані #1
6
Джерело III Міжнародна Літня школа програмування 2012 м. Севастополь