AT_abc408_e.[ABC408E] Minimum OR Path

给定一个连通无向图，该图有 $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$。

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

约束

• $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 提示：

该图可能包含重边。