题目描述

给定一个连通无向图，该图有 $N$ 个顶点和 $M$ 条边，且无自环，顶点编号从 $1$ 到 $N$，边编号从 $1$ 到 $M$。边 $i$ 双向连接顶点 $u_i$ 和 $v_i$，其边权为 $w_i$。

在从顶点 $1$ 到顶点 $N$ 的简单路径（即不会多次访问同一顶点的路径）中，求出该路径中所有边的权值的按位 $\mathrm{OR}$ 的最小可能值。

什么是按位 $\mathrm{OR}$ 运算？

非负整数 $A$ 和 $B$ 的按位 $\mathrm{OR}$，即 $A\ \mathrm{OR}\ B$，定义如下：

• 如果 $A$ 和 $B$ 的二进制表示中 $2^k$ 位至少有一位为 $1$，则 $A\ \mathrm{OR}\ B$ 的二进制表示中 $2^k(k \geq 0)$ 位上的数字为 $1$，否则为 $0$。

例如，$3\ \mathrm{OR}\ 5 = 7$（二进制表示为：$011\ \mathrm{OR}\ 101 = 111$）。 一般而言，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$的按位 $\mathrm{OR}$ 定义为 $(\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k)$，并且可以证明这与 $p_1, p_2, p_3, \dots p_k$ 的顺序无关。

输入格式

输入来自标准输入，格式如下：

• 第一行两个整数 $N,M$。
• 接下来 $M$ 行每行三个整数，分别表示 $u_i,v_i,w_i$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

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

输出 #2

4

输入输出样例 #3

输入 #3

8 12
4 5 16691344
5 7 129642441
2 7 789275447
3 8 335307651
3 5 530163333
5 6 811293773
3 8 333712701
1 2 2909941
2 3 160265478
5 7 465414272
1 3 903373004
6 7 408299562

输出 #3

468549631

说明/提示

约束

• $2\le N\le 2*10^5$
• $N-1\le M\le 2*10^5$
• $1\le u_i\le v_i\le N$
• $0\le w_i\le2^{30}$
• 给定图为连通图。
• 所有输入值均为整数。

样例 1 提示：

按顺序遍历边 $1,3,5$，并按顺序访问顶点 $1,2,3,4$，最终的按位 $\mathrm{OR}$ 为 $1\ \mathrm{OR}\ 2\ \mathrm{OR}\ 3=3$。

不可能使按位 $\mathrm{OR}$ 小于 $3$，因此输出 $3$。

样例 2 提示：

该图可能包含重边。