배낭 친구

신중한 Day 씨와 모험을 좋아하는 Knight 박사는 배낭여행 친구가 되어 아름다운 노르웨이 산맥으로 트레킹을 떠나기로 했다. 두 사람은 당연히 노르웨이 트레킹 협회(DNT)가 표시한 산길을 따라간다. 이 산길은 모두 숙박할 수 있는 오두막에서 시작해 오두막에서 끝난다.

Day 씨는 편하게 자는 것을 좋아해서 매일 밤 오두막에서 자자고 바로 제안했다.

하지만 Knight 박사의 생각은 달랐다. 매일 가능한 한 오래 걸으면 목적지에 훨씬 빨리 도착할 수 있고, 필요하면 두 오두막 사이에서 텐트를 치고 자면 된다는 것이었다. Day 씨도 목적지에 빨리 도착하는 것은 바람직하다고 동의했지만, 제대로 된 침대에서 자는 편안함을 포기할 생각은 없었다.

격렬한 논쟁 끝에 두 사람은 헤어져 각자 자기 방식대로 가기로 했다. 두 사람의 걸음 속도가 같다고 할 때, Day 씨가 도착하기까지 Knight 박사는 목적지에서 몇 시간을 기다려야 하는가?

첫 줄에 두 정수 $n$ ($1 \le n \le 100000$)과 $m$ ($1 \le m \le 100000$)이 주어진다. $n$은 오두막의 수, $m$은 산길의 수이다. 이어서 $m$개의 줄에 산길 정보가 주어진다. $i$번째 줄에는 세 정수 $u_i$, $v_i$, $d_i$ ($0 \le u_i, v_i < n$, $0 \le d_i \le 12$)가 주어지며, 이는 오두막 $u_i$와 오두막 $v_i$ 사이에 산길이 있고 그 길을 지나는 데 정확히 $d_i$시간이 걸린다는 뜻이다. 두 오두막 사이에 산길이 여러 개 있을 수 있고, 산길이 출발한 오두막으로 되돌아올 수도 있다.

Day 씨와 Knight 박사는 오두막 0에서 출발하며, 목적지는 오두막 $n-1$이다. 매일 08:00에 걷기 시작해서, 밤이 되어 쉬기 전까지 최대 12시간 동안 쉬지 않고 걷는다.

Day 씨가 도착할 때까지 Knight 박사가 목적지에서 기다려야 하는 시간을 시간 단위의 정수 하나로 출력한다.