Задача по ориентированному графу

Вам задан ориентированный граф G. Каждое ребро имеет некоторую пропускную способность. Найдите максимальный поток между вершинами 1 и n.

Формат ввода: первая строка входного файла содержит n и m — число вершин и рёбер в графе (2 ≤ n ≤ 500, 1≤ m ≤ 10000). Последующие строки описывают рёбра. Каждое ребро задается тремя числами: начальная вершина ребра, конечная вершина ребра и пропускная способность ребра. Пропускные способности — целые числа, не превосходящие 10^9.

Формат вывода: выведите величину максимального потока между вершинами 1 и n.

Ограничение времени - 1 секунда. Ограничение памяти - 64Mb.

Пример

Ввод:

6 9

1 2 8

1 3 9

2 3 3

2 5 4

5 3 5

3 4 2

4 5 4

4 6 9

5 6 10

Вывод:

6