31840번 - 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페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.