#P18668. MEXimum Spanning Tree
MEXimum Spanning Tree
MEXimum Spanning Tree
最大生成树是计算机科学中的经典问题。有一天,Grammy 想到了一个新变种:给定一张带权图,寻找一棵生成树,使生成树上所有边权组成的集合的 MEX 最大。
一个集合的 MEX(Minimum EXcluded natural number)是没有出现在该集合中的最小非负整数。例如,,,。
请帮助 Grammy 求出最大的 MEX。
输入格式
第一行包含两个整数 ,分别表示顶点数和边数,满足 、。
接下来 行,每行包含三个整数 ,表示顶点 、 之间有一条权值为 的无向边。其中 ,,。
保证图连通。原题没有限制重边,因此不同输入行可以连接相同的两个顶点;不能因此丢弃这些边的不同权值。 是合法输入,此时生成树不含边。
输出格式
输出一行一个整数,表示所有生成树中最大的边权 MEX。
样例输入 1
4 4
1 2 0
2 3 1
1 3 1
3 4 2
样例输出 1
3