最大生成树是计算机科学中的一个经典问题。有一天，Grammy 想出了这个问题的一个全新变体。她想要找到带权图的一棵生成树，使得该生成树边权的 MEX 最大。

集合的 MEX（Minimum EXcluded natural number，最小排除自然数）是指不在该集合中的最小自然数。例如，$\text{MEX}(\{0, 2, 4, 5, 7\}) = 1$，$\text{MEX}(\{0, 1, 2, 3, 6\}) = 4$，$\text{MEX}(\{3\}) = 0$。

请帮助 Grammy 解决这个问题。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 1000, 0 \le m \le 1000$)，分别表示顶点数和边数。

接下来的 $m$ 行中，每行包含三个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 0 \le w_i \le n$)，表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边，其权重为 $w_i$。

保证图是连通的。

输出格式

输出一个整数，表示生成树的最大 MEX。

样例

输入 1

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

输出 1

3