왕복 여행

N개의 나라와 M개의 양방향 도로가 있다. 나라는 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)

두 나라 사이에는 도로가 최대 한 개만 주어진다. 입력은 항상 조건을 만족하는 왕복 여행이 가능한 경우만 주어진다.

첫째 줄에 왕복 여행에 필요한 최소 시간을 출력한다.

주어진 입력에서는 1-2-4-3-1 순서로 이동하면 총 시간이 10이다. 조건을 만족하면서 10보다 적은 시간으로 왕복할 수는 없다.