16707번 - American Tour

승한이는 올해 졸업을 기념하여 처음으로 미국을 가보기로 했다. 

여행을 떠나기 전, 승한이는 미국 여행에서 관광 명소, 호텔, 공항 등 중요한 N개의 위치를 미리 알아놓았다. 

이 N개의 위치는 1번, 2번, ... , N번으로 각각 번호가 붙어있고, 총 M개의 도로로 연결되어 있다고 한다. 

단, 모든 도로는 양방향 통행이 가능하고, 두 위치를 잇는 도로가 여러 개 존재할 수 있다고 한다.

미국에 도착한 승한이는 말로만 들어본 자유의 여신상을 꼭 보고 싶어서 자유의 여신상을 보고 숙소로 이동하고자 한다.

또한, 승한이는 많은 것을 구경하고 싶어 자유의 여신상을 거쳐 숙소로 가는 동안, 같은 길을 두 번 이상 이용하지 않을 것이다. 단, 같은 위치를 여러 번 방문하는 것은 허용된다.

승한이는 1번 위치에서 출발하고, 자유의 여신상은 2번 위치, 숙소는 N번 위치라고 한다.  

미국의 지도가 주어졌을 때 승한이가 조건에 맞게 자유의 여신상을 지나 숙소로 돌아가는 가장 짧은 경로의 길이를 구해보자.

단, 자유의 여신상으로 가는 도중에 숙소를 지나치는 것은 허용되며, 승한이의 조건에 맞는 경로가 적어도 하나는 존재함이 보장된다. 

첫째 줄에는 위치의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1000, 2 ≤ M ≤ 10000)

다음 M개의 줄에는 각 도로가 있는 위치의 번호 s_i, e_i와 도로의 길이 d_i가 주어진다. (1 ≤ s_i, e_i ≤ N, 1 ≤ d_i ≤ 10000)

단, 1번 위치는 승한이의 출발점이고, 2번 위치는 자유의 여신상, N번 위치는 숙소이다. 

출발점에서 자유의 여신상을 거쳐 숙소로 가는 가장 짧은 경로의 길이를 출력한다.