Description

$\textit{Pang}$ 的研究兴趣之一是最大流问题。

一个有 $n$ 个顶点的有向图 $G$ 被称为 $\textit{universe}$，如果满足以下条件：

• $G$ 是 $k$ 条从顶点 $1$ 到顶点 $n$ 的顶点互不相交、长度相同的简单路径的并集。

一组路径是顶点互不相交的，如果它们没有任何内部顶点相同。

路径中的一个顶点被称为内部顶点，如果它不是该路径的端点。

一条路径是简单的，如果其顶点互不相同。

设 $G$ 是一个有 $n$ 个顶点、$m$ 条边的 $\textit{universe}$ 图。每条边都有一个非负整数容量。你可以进行如下操作任意次（包括 $0$ 次），以使从顶点 $1$ 到顶点 $n$ 的最大流尽可能大：

设 $e$ 是一条容量大于 $0$ 的边。将 $e$ 的容量减少 $1$，并将另一条边的容量增加 $1$。

$\textit{Pang}$ 想知道，最少需要多少次操作才能实现最大流最大化？

Input Format

第一行包含两个整数 $n$ 和 $m$（$2\leq n\leq 100000, 1\leq m \leq 200000$）。

接下来的 $m$ 行，每行包含三个整数 $x, y, z$，表示一条从 $x$ 到 $y$ 的有向边，容量为 $z$（$1 \leq x, y \leq n$, $0\le z\le 1000000000$）。

保证输入是一个 $\textit{universe}$ 图，没有重边和自环。

Output Format

输出一个整数，表示最少需要的操作次数。

4 3
1 2 1
2 3 2
3 4 3

1

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

1

Hint

由 ChatGPT 4.1 翻译