시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 78 15 12 19.048%

문제

지민이는 대지주 정문이 집에 놀러갔다. 하지만 테러리즘에 빠져있는 지민이는 가방 속에 한가득 지뢰를 들고 정문이 농장에 놀러 갔다.

이런 속마음도 모르는 정문이는 지민이에게 자신이 관리하는 N개의 농장을 관광시켜주려 한다. N개의 농장은 1번부터 N번까지 번호가 붙여져 있고 이 농장 사이에는 M개의 도로가 놓여있다.

현재 지민이와 정문이는 1번 농장에 있고 N번 농장을 방문한 다음 1번 농장으로 다시 돌아오려 한다. 그리고 방문하는 동안 지민이는 자신이 지나간 길에 지뢰를 심으려 한다.

지민이가 지뢰를 심는 사실이 발각되면 심각한 상황에 놓일 수 있기 때문에 가능한 한 빨리 농지를 관광하고 돌아오려 한다. 하지만 이미 지나간 길은 지뢰가 놓여 있기 때문에 다시 그 길을 지나가기를 원치 않는다.

문제는 각 길마다 그 길을 지나가는 시간이 주어졌을 때 최소로 농지를 관광하고 돌아오는 시간을 알고 싶어 한다.

입력

첫째 줄에는 자연수 N(3≤N≤1,000), M(2≤M≤10,000)이 주어진다. N은 농지의 개수이고 M은 도로의 개수를 나타낸다. 다음 M개의 줄에는 도로의 정보를 나타내는 세 자연수 P, Q, L(1≤L≤35,000)이 주어진다. 이는 P번 도시와 Q번 도시 사이에 도로가 있으며, 이를 지날 때 소요되는 시간이 L임을 의미한다.

출력

첫째 줄에 농지를 관광하는 최소 시간을 출력한다.

예제 입력

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

예제 출력

6

힌트

출처

  • 문제를 번역한 사람: author6