Задачи
Максимальный поток 2
Максимальный поток 2
Вам задан ориентированный граф \textbf{G}. Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами \textbf{1} и \textbf{n}.
\InputFile
Первая строка входного файла содержит \textbf{n} и \textbf{m} - число вершин и рёбер в графе (\textbf{2} ≤ \textbf{n} ≤ \textbf{500}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10000}). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности не превосходят \textbf{10^9}.
\OutputFile
Выведите величину максимального потока между вершинами \textbf{1} и \textbf{n}.
Входные данные #1
4 5 1 2 1 1 3 2 3 2 1 2 4 2 3 4 1
Выходные данные #1
3