문제
아프리카를 주름잡는 타잔은 나무에 줄을 매달아 놓고 그 줄을 이용해 나무 사이를 이동한다.
두 나무 사이를 이동하기 위해서는 나무의 높이, 나무사이의 거리, 주변의 방해물 등에 의해서
이동하기 위해 필요한 체력이 결정되며 아예 이동이 불가능한 곳도 있다.
N개의 나무는 1번부터 N번까지 번호가 붙여져 있고 이동이 가능한 나무 사이에는 이동을 위해서 필요한 최소한의 체력이 주어진다.
타잔은 K개의 튼튼한 밧줄이 있어서 이동이 가능한 나무 사이에 밧줄을 연결해서 연결된 나무 사이에는 체력 상관없이 이동할 수 있다.
타잔은 특이한 체질이라서 여러 곳을 이동하더라도 항상 동일한 체력이 유지된다.
타잔이 1번 나무로부터 N번 나무까지 이동하기 위해 필요한 최소의 체력이 얼마인지 구하는 프로그램을 작성하라.
입력
첫 줄에 나무의 개수 N(1 ≤ N ≤ 1,000)과 이동이 가능한 구간의 개수 M(1 ≤ M ≤ 10,000)
그리고 나무 사이를 연결할 수 있는 밧줄의 개수 K(0 ≤ K < N)가 주어진다.
둘째 줄부터 M개의 줄에는 각각 세 개의 정수가 a, b, c가 주어지는데
a나무에서 b나무로 이동하기 위해 필요한 체력이 c임을 나타낸다.
(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1,000,000)
출력
1번 나무로부터 N번나무까지 이동하기 위해 필요한 최소 체력을 출력한다.
이동이 불가능한 경우에는 -1을 출력한다.
예제
5 6 1
1 2 2
2 3 3
3 1 6
4 1 4
3 4 7
4 5 3
3
힌트
로그인해야 코드를 작성할 수 있어요.