Pang 的研究兴趣之一是最大流问题。

如果一个有 $n$ 个顶点的有向图 $G$ 满足以下条件，则称其为 universe 图： * $G$ 是 $k$ 条从顶点 $1$ 到顶点 $n$ 的长度相同的顶点不交简单路径的并集。

如果一组路径没有公共的内部顶点，则称这组路径是顶点不交的。 路径中的顶点如果不是该路径的端点，则被称为内部顶点。 如果路径中的顶点互不相同，则称该路径是简单的。

设 $G$ 是一个具有 $n$ 个顶点和 $m$ 条边的 universe 图。每条边都有一个非负整数容量。你可以执行以下操作任意次（包括 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

1

样例输入 2

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

样例输出 2

1