Dany jest spójny graf nieskierowany złożony z $n$ wierzchołków i $m$ krawędzi. $i$-ta krawędź ma nieujemną wagę całkowitą $w_i$. Należy znaleźć drzewo rozpinające tego grafu takie, aby mex zbioru wag krawędzi w drzewie rozpinającym był jak najmniejszy.

Wejście

Pierwszy wiersz wejścia zawiera dwie dodatnie liczby całkowite $n$ oraz $m$ ($1 \le n \le 5 \times 10^5$, $1 \le m \le 10^6$).

W kolejnych $m$ wierszach znajdują się po trzy nieujemne liczby całkowite $u$, $v$ oraz $w$ ($1 \le u, v \le n$, $u \ne v$, $0 \le w \le n-1$), oznaczające, że pomiędzy wierzchołkami $u$ i $v$ istnieje krawędź o wadze $w$.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę całkowitą — odpowiedź.

Przykład

Wejście

2 2
1 2 0
1 2 1

Wyjście

0

Wejście

5 7
1 2 0
1 3 0
2 4 1
2 5 0
3 4 2
3 5 0
4 5 1

Wyjście

1