Рассмотрим ациклический ориентированный граф G, с каждым ребром которого uv связана пропускная способность c(uv). Пусть G имеет две специальные вершины: исток s и сток t.

Потоком в G называется функция f : E -> R такая что следующие условия имеют место:

1. 0 ≤ f(uv) ≤ c(uv) для всех ребер uv.

2. для всякой вершины u кроме s и t

Величина потока f обозначается как |f| - количество потока, исходящего из истока:

Поток называется максимальным если |f| наибольшее возможное среди всех потоков в G. Очевидно, что может существовать несколько максимальных потоков.

Потоки могут быть сложены поточечно или умножены на действительную константу, как и на любые другие функции. Зафиксируем некоторый максимальный поток fmax. Говорят, что множество потоков {f1, f2, ..., fn} образуют базис максимальных потоков, если каждый максимальный поток можно представить в виде суммы

и никакое его подмножество не имеет этого свойства. Здесь ai принадлежит R.

Размер этого множества - n - называется размерностью максимальных потоков графа.

По заданному графу G найдите размерность его максимальных потоков.

Входные данные

Первая строка содержит n и m - количество вершин и ребер в графе (1 ≤ n ≤ 10, 1 ≤ m ≤ 10). Каждая из следующих m строк содержит три целых числа и описывает ребра. Каждое ребро описывается исходящей вершиной, входящей вершиной и его пропускной способностью. Граф ациклический. Исток имеет номер 1, сток имеет номер n. Пропускные способности не превосходят 104. Гарантируется, что существует путь из истока в сток.

Выходные данные

Выведите максимальную размерность максимальных потоков заданного графа.