Вам задан ориентированный граф $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
Сдать: для сдачи задач необходимо войти в систему