지민이의 농장 여행 Season II

지민이는 대지주 정문이의 집에 놀러 갔다. 정문이는 자신이 관리하는 N개의 농장을 지민이에게 보여 주려고 한다. 농장은 1번부터 N번까지 번호가 붙어 있고, 농장 사이에는 M개의 양방향 도로가 있다.

두 사람은 현재 1번 농장에 있다. 지민이는 N번 농장을 방문한 뒤 다시 1번 농장으로 돌아오려고 한다. 그런데 지민이는 자신이 지나간 도로마다 지뢰를 묻으려 하므로, 이미 지나간 도로를 다시 지나가고 싶어 하지 않는다.

각 도로를 지나는 데 걸리는 시간이 주어질 때, 1번 농장에서 출발해 N번 농장을 방문하고 1번 농장으로 돌아오는 데 필요한 최소 시간을 구하라. 단, 같은 도로는 두 번 이상 지나갈 수 없다.

첫째 줄에 자연수 N과 M이 주어진다. N은 농장의 개수, M은 도로의 개수이다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000)

다음 M개의 줄에는 도로 정보를 나타내는 세 자연수 P, Q, L이 주어진다. 이는 P번 농장과 Q번 농장 사이에 도로가 있으며, 이 도로를 지나는 데 L의 시간이 걸린다는 뜻이다. (1 ≤ L ≤ 35,000)

항상 조건을 만족하는 왕복 경로가 존재하는 입력만 주어진다.

1번 농장에서 출발해 N번 농장을 방문하고 다시 1번 농장으로 돌아오는 최소 시간을 출력한다.