Traveling SCCC President 2

Sangwon, the president of SCCC, a problem-solving club in the Department of Computer Science and Engineering at Soongsil University, wants to walk from the Information Science Building to the Hyeongnam Engineering Building to put up contest promotion posters.

The Soongsil University campus has $N$ buildings numbered $1$ to $N$ and $M$ roads numbered $1$ to $M$. Each road connects two different buildings. The $i$-th road connects building $u_i$ and building $v_i$, and its length is $w_i$. At most one road connects any pair of buildings, and every building can be reached from every other building by roads. The Information Science Building is building $1$, and the Hyeongnam Engineering Building is building $N$.

An ordinary person spends time equal to the sum of the road lengths used to travel between buildings. Sangwon, however, spends time equal to the bitwise OR of all the road lengths used. Find the minimum time Sangwon needs to travel from building $1$ to building $N$.

The first line contains the number of buildings $N$ and the number of roads $M$, separated by a space.

From the second line onward, each of the next $M$ lines contains the two buildings $u_i, v_i$ connected by the $i$-th road and its length $w_i$, separated by spaces.

Print the minimum time Sangwon needs to travel from building $1$ to building $N$.

• $2 \le N \le 300\,000$
• $N-1 \le M \le 300\,000$
• $1 \le u_i, v_i \le N$, $u_i \ne v_i$ $(1 \le i \le M)$
• $0 \le w_i < 2^{60}$ $(1 \le i \le M)$
• If $i \ne j$, then $(u_i, v_i) \ne (u_j, v_j)$ and $(u_i, v_i) \ne (v_j, u_j)$. No two roads connect the same pair of buildings.
• Every building is connected to the others by roads.
• All input values are integers.

For two integers $A$ and $B$, the bitwise OR $A\text{ OR }B$ is defined as follows. In binary, if at least one of the $2^k$ digits of $A$ and $B$ is 1, then the $2^k$ digit of $A\text{ OR }B$ is 1. If both are 0, the $2^k$ digit of $A\text{ OR }B$ is 0.

For example, $12=1100_{(2)}$ and $10=1010_{(2)}$, so $12\text{ OR }10=1100_{(2)}\text{ OR }1010_{(2)}=1110_{(2)}=14$.

The bitwise OR of $k$ integers $A_1, A_2, \cdots, A_k$ is defined as $(\cdots((A_1\text{ OR }A_2)\text{ OR }A_3)\text{ OR }\cdots)\text{ OR }A_k$. You can prove that this result does not change when the order of $A_1, \ldots, A_k$ is changed.

Road lengths and the answer can exceed the 32-bit integer range, so C/C++ users should use the long long type and Java users should use the long type.

Because the input and output are large, using fast I/O as described in the language guide on pages 2 to 4 of the problem booklet is recommended.