Traveling SCCC President 2

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

숭실대학교의 캠퍼스는 $1$번부터 $N$번까지 번호가 붙어 있는 $N$개의 건물과, 서로 다른 두 건물을 연결하고 $1$번부터 $M$번까지 번호가 붙어 있는 $M$개의 도로로 구성되어 있다. $i$번째 도로는 $u\_i$번 건물과 $v\_i$번 건물을 연결하고, 이 도로의 길이는 $w\_i$이다. 두 건물 쌍을 연결하는 도로는 최대 한 개만 존재하며, 모든 건물은 도로를 통해 서로 이동할 수 있다. 정보과학관의 건물 번호는 $1$번, 형남공학관의 건물 번호는 $N$번이다.

일반적인 사람이라면 다른 건물로 이동할 때 사용한 도로 길이의 합 만큼의 시간이 소요되겠지만, 놀랍게도 상원이는 사용한 도로의 길이를 모두 bitwise OR 연산한 값 만큼의 시간이 소요된다. 상원이가 $1$번 건물에서 $N$번 건물로 이동할 때 걸리는 최소 시간을 구해주자.

bitwise OR 연산이 무엇인지 잘 모르는 친구들은 문제 지문 맨 아래에 친절한 정휘가 준비해 놓은 정의를 읽어보도록 하자.

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

둘째 줄부터 $M$개의 줄에 걸쳐, $i$번 도로가 연결하는 두 건물의 번호 $u\_i,v\_i$와 도로의 길이 $w\_i$가 한 줄에 하나씩 공백으로 구분되어 주어진다.

상원이가 $1$번 건물에서 $N$번 건물로 이동하는 데 필요한 최소 시간을 출력한다.

• $2\leq N\leq 300\\, 000$
• $N-1\leq M\leq 300\\, 000$
• $1\leq u\_i,v\_i\leq N$, $u\_i\neq v\_i$ $(1\leq i\leq M)$
• $0\leq w\_i<2^{60}$ $(1\leq i\leq M)$
• $i\neq j$면 $(u\_i,v\_i)\neq(u\_j,v\_j)$, $(u\_i,v\_i)\neq(v\_j,u\_j)$이다. 즉, 연결하는 두 건물의 쌍이 같은 도로가 여러 개 존재하지 않는다.
• 모든 건물은 도로를 통해 이어져 있다.
• 입력으로 주어지는 수는 모두 정수이다.

두 정수 $A,B$를 bitwise OR한 값 $A\text{ OR } B$는 다음과 같이 정의된다.

• 이진법으로 생각했을 때, $A$의 $2^k$의 자릿수와 $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$로 계산된다.

$k$개의 정수 $A\_1,A\_2,\cdots ,A\_k$를 bitwise OR한 결과는 $(\ldots((A\_1\text{ OR } A\_2)\text{ OR } A\_3)\text{ OR }\ldots)\text{ OR } A\_k$로 정의된다. 이 연산의 결과는 $A\_1,A\_2,\cdots ,A\_k$의 순서를 바꾸더라도 변하지 않음을 증명할 수 있다.

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

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