最小mex生成树

这是一道经典题。

给定 $n$ 个点 $m$ 条边的无向连通图，边有边权。 设一个自然数集合 $S$ 的 $\text{mex}$ 为：最小的、没有出现在 $S$ 中的自然数。 现在你要求出一个这个图的生成树，使得其边权集合的 $\text{mex}$ 尽可能小。

第一行输入两个正整数 $n,m$。 接下来 $m$ 行，每行 $3$ 个非负整数 $u,v,w$，表示 $u,v$ 之间有一条权值为 $w$ 的边。

输出一行一个自然数，表示最小的 $\text{mex}$ 值。

3 3
1 2 0
2 3 1
3 2 2

1

【数据范围】 - 对于 $20\%$ 的数据，$1\le n \le 100$，$1\le m \le 200$。 - 对于 $50\%$ 的数据，$1\le n \le 2000$，$1\le m \le 3000$。 - 对于 $80\%$ 的数据，$1\le n \le 10^5$，$1\le m \le 2\times 10^5$。 - 对于 $100\%$ 的数据，$1\le n \le 10^6$，$1\le m \le 2\times 10^6,0\le w \le 10^5$。 输入数据规模较大，建议使用高效的读入方式。