문제
농부 창호의 친구들이 그의 농장을 방문해서, 창호는 친구들에게 농장 구경을 시켜주기로 했다. 창호의 농장은 N(1 <= N <= 1,000)개의 목초지로 되어 있고, 각각의 번호는 1부터 N까지 차례로 매겨져 있다. 그리고 1번 목초지는 창호의 집과 연결되어 있고, N번 목초지는 큰 헛간과 연결되어 있다. 총 M(1 <= M <= 10,000)개의 양방향 길이 이들 목초지를 잇고 있다. 각각의 길은 두 개의 서로 다른 목초지를 잇고, 그 길이는 35,000 이하의 양의 정수이다.
창호는 그의 집에서 출발하여 몇 개의 길을 거쳐 농장에서 잠깐 쉬기로 했다. 그 뒤에 다시 몇 개의 길을 거쳐 집으로 돌아오려고 한다. 창호는 여행의 총 길이가 최소가 되기를 원하지만, 하나의 길을 두 번 이상 사용하는 것은 원하지 않는다.
여행의 최소 길이를 구하자. 답은 항상 존재한다.
입력
첫 번째 줄에 공백으로 구분된 두 개의 정수 N과 M이 입력된다.
이후 M개의 줄에 걸쳐 길을 나타내는 세 개의 정수가 공백으로 구분되어 입력된다. 이는 각각 길의 한쪽 끝, 다른 쪽 끝, 길의 길이를 나타낸다.
출력
여행의 최소 길이를 출력한다.
예제
4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
6
로그인해야 코드를 작성할 수 있어요.