Jednym z zainteresowań badawczych Panga jest problem przepływu maksymalnego.

Skierowany graf $G$ o $n$ wierzchołkach nazywamy universe, jeśli spełniony jest następujący warunek: * $G$ jest sumą $k$ wierzchołkowo rozłącznych ścieżek prostych z wierzchołka $1$ do wierzchołka $n$, mających tę samą długość.

Zbiór ścieżek jest wierzchołkowo rozłączny, jeśli ścieżki nie mają żadnego wspólnego wierzchołka wewnętrznego. Wierzchołek w ścieżce nazywamy wewnętrznym, jeśli nie jest on końcem tej ścieżki. Ścieżka jest prosta, jeśli wszystkie jej wierzchołki są różne.

Niech $G$ będzie grafem universe o $n$ wierzchołkach i $m$ krawędziach. Każda krawędź ma nieujemną całkowitą przepustowość. Możesz wykonać następującą operację dowolną liczbę razy (w tym zero), aby zmaksymalizować przepływ maksymalny z wierzchołka $1$ do wierzchołka $n$:

Wybierz krawędź $e$ o dodatniej przepustowości. Zmniejsz przepustowość $e$ o $1$ i zwiększ przepustowość innej krawędzi o $1$.

Pang chce wiedzieć, jaka jest minimalna liczba operacji potrzebna do osiągnięcia tego celu.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 100000$, $1 \le m \le 200000$).

Każda z kolejnych $m$ linii zawiera trzy liczby całkowite $x$, $y$ oraz $z$, oznaczające krawędź z $x$ do $y$ o przepustowości $z$ ($1 \le x, y \le n$, $0 \le z \le 1000000000$).

Gwarantuje się, że dane wejściowe opisują graf universe bez wielokrotnych krawędzi i pętli własnych.

Wyjście

Wypisz jedną liczbę całkowitą — minimalną liczbę operacji.

Przykład

Wejście 1

4 3
1 2 1
2 3 2
3 4 3

Wyjście 1

1

Wejście 2

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

Wyjście 2

1