택배 기사가 1번 마을에서 N번 마을까지 가려고 해요. 마을 사이 길마다 통행료가 달라요. 통행료 합이 가장 적게 드는 경로의 비용을 구하세요.
힌트: 거쳐 가는 길의 수가 아니라 비용의 합이 가장 작아야 해요. 다익스트라 알고리즘을 찾아보세요!
입력
첫째 줄에 마을 수 N과 길 수 M이 주어져요. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 5,000) 다음 M개의 줄에 길 정보 u v w가 주어져요 — u 마을과 v 마을을 잇는 통행료 w의 양방향 길이에요. (1 ≤ w ≤ 1,000)
출력
1번에서 N번까지 가는 최소 비용을 출력해요. 갈 수 없으면 -1을 출력해요.