小明游玩到了异世界，这个异世界太复杂了，里面有很多个国家，国家之间建设有各种各样的通路。

异世界的神看国家之间的交流过于频繁，害怕异世界老百姓联合起来抵抗神。

神想破坏一些通道，让下届的老百姓至少分割成两个区域，不要频繁交流。

所以但是神不敢给与破坏者太大的神力，他想知道破坏者最少需要多少破坏力才可以把世界分成两个区域！（破坏力的意思是，他能破坏$100$的路，那就可以破坏$100$以下的所有的路，而100以上的是不行的）！

第一行两个数字，n和m，分别表示n个国家和m个通道；

接下来m行，每行3个数字，a,b,c，分别表示a国到b国的道路需要c点神力才可以破坏

一个数字，表示神力至少需要多少

样例解释：

破坏者需要破坏，(1,2),(1,3),(3,2),(4,2)这四组边以后，2就会和13 4变成两个世界，所以破坏者需要的神力是4。

30%的数据，n\leq 1000,m\leq 3000

70%的数据，n\leq 10^6,m\leq 10^6