미국 여행

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

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

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

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

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

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

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

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

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

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

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

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

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