题目背景
这是一道经典题。
题目描述
给定 n 个点 m 条边的无向连通图,边有边权。
设一个自然数集合 S 的 mex 为:最小的、没有出现在 S 中的自然数。
现在你要求出一个这个图的生成树,使得其边权集合的 mex 尽可能小。
输入格式
第一行输入两个正整数 n,m。
接下来 m 行,每行 3 个非负整数 u,v,w,表示 u,v 之间有一条权值为 w 的边。
输出格式
输出一行一个自然数,表示最小的 mex 值。
3 3
1 2 0
2 3 1
3 2 2
1
提示
【数据范围】
- 对于 20% 的数据,1≤n≤100,1≤m≤200。
- 对于 50% 的数据,1≤n≤2000,1≤m≤3000。
- 对于 80% 的数据,1≤n≤105,1≤m≤2×105。
- 对于 100% 的数据,1≤n≤106,1≤m≤2×106,0≤w≤105。
输入数据规模较大,建议使用高效的读入方式。