Traveling SCCC President 2

숭실대학교 컴퓨터학부 문제해결 소모임 SCCC의 회장 상원이는 대회 홍보 포스터를 붙이려고 정보과학관에서 형남공학관까지 이동하려고 한다.

숭실대학교 캠퍼스에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 건물과 $1$번부터 $M$번까지 번호가 붙은 $M$개의 도로가 있다. 각 도로는 서로 다른 두 건물을 잇는다. $i$번 도로는 $u_i$번 건물과 $v_i$번 건물을 잇고, 길이는 $w_i$이다. 두 건물을 잇는 도로는 최대 한 개이며, 모든 건물은 도로를 통해 서로 이동할 수 있다. 정보과학관은 $1$번 건물, 형남공학관은 $N$번 건물이다.

보통 사람은 건물 사이를 이동할 때 사용한 도로 길이의 합만큼 시간이 걸린다. 그런데 상원이는 사용한 도로 길이를 모두 bitwise OR 연산한 값만큼 시간이 걸린다. 상원이가 $1$번 건물에서 $N$번 건물까지 이동하는 데 걸리는 최소 시간을 구하라.

첫째 줄에 건물 개수 $N$과 도로 개수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐, $i$번 도로가 잇는 두 건물 번호 $u_i, v_i$와 도로 길이 $w_i$가 한 줄에 하나씩 공백으로 구분되어 주어진다.

상원이가 $1$번 건물에서 $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)$
• $i \ne j$이면 $(u_i, v_i) \ne (u_j, v_j)$이고 $(u_i, v_i) \ne (v_j, u_j)$이다. 같은 두 건물을 잇는 도로는 여러 개 없다.
• 모든 건물은 도로를 통해 이어져 있다.
• 입력으로 주어지는 수는 모두 정수이다.

두 정수 $A$, $B$의 bitwise OR 값 $A\text{ OR }B$는 다음과 같이 정의한다. 이진법으로 나타냈을 때, $A$와 $B$의 $2^k$ 자릿수 중 하나 이상이 1이면 $A\text{ OR }B$의 $2^k$ 자릿수는 1이다. 둘 다 0이면 $A\text{ OR }B$의 $2^k$ 자릿수는 0이다.

예를 들어 $12=1100_{(2)}$, $10=1010_{(2)}$이므로 $12\text{ OR }10=1100_{(2)}\text{ OR }1010_{(2)}=1110_{(2)}=14$이다.

정수 $A_1, A_2, \cdots, A_k$의 bitwise OR 결과는 $(\cdots((A_1\text{ OR }A_2)\text{ OR }A_3)\text{ OR }\cdots)\text{ OR }A_k$로 정의한다. 이 결과는 $A_1, \ldots, A_k$의 순서를 바꿔도 변하지 않음을 증명할 수 있다.

도로 길이와 정답은 32비트 정수 범위를 벗어날 수 있으므로, C/C++에서는 long long 타입을, Java에서는 long 타입을 쓰는 것을 권장한다.

입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.