$n$ 個の頂点と $m$ 本の辺からなる、連結な無向グラフが与えられる。 $i$ 番目の辺には非負整数の重み $w_i$ が付いている。
このグラフの 全域木に含まれる辺の重みの集合の mex ができるだけ小さくなるような全域木を求めよ。
入力
入力の 1 行目には、2 つの正の整数 $n$ と $m$ $(1 \le n \le 5 \times 10^5,\ 1 \le m \le 10^6)$ が与えられる。
続く $m$ 行のそれぞれには、3 つの非負整数 $u,\ v,\ w$ $(1 \le u, v \le n,\ u \ne v,\ 0 \le w \le n-1)$ が与えられ、 頂点 $u$ と $v$ の間に重み $w$ の辺が存在することを表す。
出力
答えを表す整数を 1 行に出力せよ。
例
入力
2 2 1 2 0 1 2 1
出力
0
入力
5 7 1 2 0 1 3 0 2 4 1 2 5 0 3 4 2 3 5 0 4 5 1
出力
1