Pang 的研究興趣之一是最大流問題。

若一個具有 $n$ 個頂點的有向圖 $G$ 滿足以下條件，則稱其為 universe 圖：

• $G$ 是 $k$ 條從頂點 $1$ 到頂點 $n$ 且長度相同的頂點獨立簡單路徑的聯集。

若一組路徑沒有共同的內部頂點，則稱其為頂點獨立。 路徑中的頂點若不是該路徑的端點，則稱為內部頂點。 若路徑中的頂點皆不重複，則稱該路徑為簡單路徑。

令 $G$ 為一個具有 $n$ 個頂點與 $m$ 條邊的 universe 圖。每條邊都有一個非負整數容量。 你可以執行以下操作任意次（包含 0 次），以使從頂點 $1$ 到頂點 $n$ 的最大流盡可能大：

令 $e$ 為一條容量大於 $0$ 的邊。將 $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