You are given a connected undirected graph with $n$ vertices and $m$ edges. The $i$-th edge has a non-negative integer weight $w_i$. Find a spanning tree of the graph such that the mex of the set of edge weights in the spanning tree is as small as possible.

Input

The first line of the input contains two positive integers $n$ and $m$ ($1 \le n \le 5 \times 10^5$, $1 \le m \le 10^6$).

The next $m$ lines each contain three non-negative integers $u$, $v$, and $w$ ($1 \le u, v \le n$, $u \ne v$ $0 \le w \le n-1$), indicating that there is an edge between vertices $u$ and $v$ with weight $w$.

Output

Output a single line with a single integer, indicating the answer.

Example

Input

2 2
1 2 0
1 2 1

Output

0

Input

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

Output

1