#P18668. MEXimum Spanning Tree

MEXimum Spanning Tree

MEXimum Spanning Tree

最大生成树是计算机科学中的经典问题。有一天,Grammy 想到了一个新变种:给定一张带权图,寻找一棵生成树,使生成树上所有边权组成的集合的 MEX 最大。

一个集合的 MEX(Minimum EXcluded natural number)是没有出现在该集合中的最小非负整数。例如,MEX⁡({0,2,4,5,7})=1\operatorname{MEX}(\{0,2,4,5,7\})=1,MEX⁡({0,1,2,3,6})=4\operatorname{MEX}(\{0,1,2,3,6\})=4,MEX⁡({3})=0\operatorname{MEX}(\{3\})=0。

请帮助 Grammy 求出最大的 MEX。

输入格式

第一行包含两个整数 n,mn,m,分别表示顶点数和边数,满足 1≤n≤10001\le n\le1000、0≤m≤10000\le m\le1000。

接下来 mm 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,表示顶点 uiu_i、viv_i 之间有一条权值为 wiw_i 的无向边。其中 1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,0≤wi≤n0\le w_i\le n。

保证图连通。原题没有限制重边,因此不同输入行可以连接相同的两个顶点;不能因此丢弃这些边的不同权值。n=1,m=0n=1,m=0 是合法输入,此时生成树不含边。

输出格式

输出一行一个整数,表示所有生成树中最大的边权 MEX。

样例输入 1

4 4
1 2 0
2 3 1
1 3 1
3 4 2

样例输出 1

3