题目描述

某城有两座监狱，共关押着 $N$ 名囚犯，编号 $1\sim N$。囚犯之间关系恶劣，部分人之间存在仇恨。我们用「怨气值」（正整数）衡量两名囚犯间的仇恨程度，怨气值越大，积怨越深。若怨气值为 $c$ 的两名囚犯被关在同一座监狱，他们每年必然发生摩擦，产生影响力为 $c$ 的冲突事件。

每年年末，警方将全年所有冲突事件按影响力从大到小排列，上报给市长。市长只看列表中第一个事件的影响力——若影响恶劣，他可能撤换警察局长。

警察局长考察了 $N$ 名囚犯间的仇恨关系后，决定将囚犯在两座监狱间重新分配，使得市长看到的那个冲突事件的影响力尽可能小。求这个最小值。

输入格式

第一行为两个正整数 $N,M$，分别表示囚犯数目和存在仇恨的囚犯对数。

接下来 $M$ 行，每行三个正整数 $a_j,b_j,c_j$，表示 $a_j$ 号与 $b_j$ 号囚犯之间存在仇恨，怨气值为 $c_j$。

数据保证 $1\le a_j \lt b_j\le N$，$0 \lt c_j\le 10^9$，且每对囚犯组合至多出现一次。

输出格式

共一行，为市长看到的那个冲突事件的最小可能影响力。若重新分配后可使所有冲突事件均不发生，则输出 $0$。

样例

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

3512

提示

数据范围

对于 $30\%$ 的数据，$N\le 15$。

对于 $70\%$ 的数据，$N\le 2\times 10^3$，$M\le 5\times 10^4$。

对于 $100\%$ 的数据，$N\le 2\times 10^4$，$M\le 10^5$。