4540 - Shortest Path2 (Challenge)

• Submit
• Status
• Discuss
• Summary

Description

여행 계획을 세우려고 한다. 반드시 가봐야 할 명소들 n개만 정해두고, 아직 출발지점과 도착지점은 정하지 않았다.

명소 0부터 명소 n-1을 모두 경유하는 최단 경로의 길이를 구해보자.

Input

* Line 1 : 명소의 갯수 n (1≤n≤1000)

* Line 2 : 경로의 갯수 N (1≤N≤100000)

* Line 3~N+2 : 명소번호 a, 명소번호 b, a에서 b까지의 거리 d (b에서 a까지 가는 거리와 다르다.) (0≤a,b≤n-1, 1≤d≤100000)

Output

* Line 1 : 명소 0부터 명소 n-1을 모두 경유하는 최단 경로의 길이를 출력한다.

Sample Input

4
12
0 1 3
0 2 4
0 3 5
1 0 6
1 2 1000
1 3 1000
2 0 7
2 1 1000
2 3 1000
3 0 1000
3 1 1000
3 2 1000

Sample Output

21

Hint

2->0->1->0->3 경로로 이동하면 거리가 21이다.