Задача №2784. Максимальный поток - 2
Вам задан ориентированный граф \(G\). Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами \(1\) и \(n\).
Входные данные
Первая строка входного файла содержит \(n\) и \(m\) — число вершин и рёбер в графе (\(2 \le n \le 500\), \(1 \le m \le 10\,000\)). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности — целые числа, не превосходящие \(10^9\).
Выходные данные
Выведите величину максимального потока между вершинами \(1\) и \(n\).
Примеры
Входные данные
4 5 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1
Выходные данные
3
Сдать: для сдачи задач необходимо войти в систему