P5631 最小mex生成树

题目背景

这是一道经典题。

题目描述

给定 $n$ 个点 $m$ 条边的无向连通图，边有边权。

设一个自然数集合 $S$ 的 $\text{mex}$ 为：最小的、没有出现在 $S$ 中的自然数。

现在你要求出一个这个图的生成树，使得其边权集合的 $\text{mex}$ 尽可能小。

输入格式

第一行输入两个正整数 $n,m$。

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

输出格式

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

输入输出样例 #1

输入 #1

3 3
1 2 0
2 3 1
3 2 2

输出 #1

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$。

输入数据规模较大，建议使用高效的读入方式。