시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 151 59 39 39.394%

문제

N개의 나라가 있고, 이들 중 몇 개의 나라들은 서로 도로로 연결되어 있다. 편의상 N개의 나라들은 각각 1, 2, ..., N의 번호가 붙어 있다고 하자. i번 나라와 j번 나라가 도로로 연결되어 있으면 i번 나라에서 j번 나라로 이동할 수 있고, j번 나라에서 i번 나라로도 이동할 수 있다. 당신은 1번 나라에 살고 있다.

여름을 맞이하여 당신은 N번 나라로 왕복 여행을 다녀오려고 한다. 즉 1번 나라에서 N번 나라로 갔다가 다시 1번 나라로 돌아오고자 한다. 아쉽게도 각 도로의 이용권이 한 장씩밖에 주어져 있지 않아서, 한 번 지난 도로는 다시 지날 수 없다고 한다. 이 때, 여행에 소요되는 최소 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3≤N≤1,000, 2≤M≤10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 도로로 연결되어 있으며, 이 도로를 지날 때 걸리는 시간이 C임을 의미한다. (1≤A≤N, 1≤B≤N, 1≤C≤50,000) 두 나라 사이에 두 개 이상의 도로가 있는 경우는 없다고 가정한다.

출력

첫째 줄에 여행에 소요되는 최소 시간을 출력한다.

예제 입력

4 5
1 2 5
1 3 2
2 3 1
2 4 2
3 4 1

예제 출력

10

힌트

1-2-4-3-1의 경로로 여행을 다녀오면 된다. 조건을 만족하면서 10 이하의 시간으로 여행을 다녀올 수는 없다.