Одной из исследовательских тем Pang является задача о максимальном потоке.

Ориентированный граф $G$ с $n$ вершинами называется universe, если выполняется следующее условие: * $G$ является объединением $k$ вершинно-независимых простых путей из вершины $1$ в вершину $n$ одинаковой длины.

Набор путей называется вершинно-независимым, если у них нет общих внутренних вершин. Вершина в пути называется внутренней, если она не является конечной точкой этого пути. Путь называется простым, если все его вершины различны.

Пусть $G$ — граф universe с $n$ вершинами и $m$ ребрами. Каждое ребро имеет неотрицательную целочисленную пропускную способность. Вы можете выполнить следующую операцию любое количество раз (в том числе 0), чтобы сделать максимальный поток из вершины $1$ в вершину $n$ как можно больше:

Выберите ребро $e$ с положительной пропускной способностью. Уменьшите пропускную способность $e$ на $1$ и увеличьте пропускную способность другого ребра на $1$.

Pang хочет узнать, какое минимальное количество операций необходимо для этого?

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

Первая строка содержит два целых числа $n$ и $m$ ($2 \le n \le 100000, 1 \le m \le 200000$). Каждая из следующих $m$ строк содержит три целых числа $x, y$ и $z$, обозначающих ребро из $x$ в $y$ с пропускной способностью $z$ ($1 \le x, y \le n, 0 \le z \le 1000000000$). Гарантируется, что входной граф является графом universe без кратных ребер и петель.

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

Выведите единственное целое число — минимальное количество операций.

Примеры

Пример 1

4 3
1 2 1
2 3 2
3 4 3

1

Пример 2

4 4
1 2 1
1 3 1
2 4 2
3 4 2

1