【题目描述】

有 N 个球迷一起坐车去看球，活动主办方准备了两辆巴士来接送球迷。虽然只有两辆，但是巴士非常大，可以容纳足够多的人。

现在主办方让你来安排球迷乘车。这是一件非常棘手的事情，因为有些球迷之间是有矛盾的。如果有矛盾的两个球迷被分到同一辆巴士中，他们俩立刻就会打起来，造成一定的破坏力。当然，没有矛盾的两个人分到同一辆车是不会打架的，有矛盾的两个人分到不同的车上也是不会打架的。

为了更好的组织乘车，你把球迷从 1 到 N 进行编号，并且调查得到了 M 条信息，每条信息形如 x y z，表示球迷 x 和球迷 y 有矛盾，他们俩分到同一辆巴士会打架造成 z 的破坏力。

可以想象，球迷上车后，可能会爆发很多次打架事件，每次打架都会造成一定的破坏力。

主办方只关心造成最大破坏力的那次打架所造成的破坏力，不妨记为 Z。

你自然希望 Z 的值尽量小，这样可以体现出你优秀的工作能力。

问：怎样安排，可以使得 Z 尽可能小呢？你只需要输出 Z 的最小值。

【输入格式】

第一行：包含两个整数 N, M

接下来 M 行：每行包含三个整数 x, y, z。数据保证 x < y，并且不会出现重复的 x y。

【输出格式】

一个整数，表示可以得到的 Z 的最小值。如果没有人打架，则输出 0。

【样例输入】

4 5
1 2 3
2 3 4
1 3 5
2 4 6
3 4 5

【样例输出】

4

【样例解释】

可能有多种方案，以下是一种可能方案：

{1,4}，{2,3}

第一辆车没有人打架，第二辆车两人打架造成的破坏力为 4。

不存在更优的方案，可以使得 Z < 4。

【数据范围 】

30% 的数据： $N ≤ 15$。

70% 的数据： $N ≤ 2000, M ≤ 50000$。

100% 的数据： $N ≤ 20000, M ≤ 100000$。数据保证 $1 ≤ x < y ≤ N, 0 < z ≤ 10^9$。