아프리카를 주름잡는 타잔은 나무에 줄을 매달아 놓고 그 줄을 이용해 나무 사이를 이동한다.

두 나무 사이를 이동하기 위해서는 나무의 높이, 나무사이의 거리, 주변의 방해물 등에 의해서

이동하기 위해 필요한 체력이 결정되며 아예 이동이 불가능한 곳도 있다.

N개의 나무는 1번부터 N번까지 번호가 붙여져 있고 이동이 가능한 나무 사이에는 이동을 위해서 필요한 최소한의 체력이 주어진다.

타잔은 K개의 튼튼한 밧줄이 있어서 이동이 가능한 나무 사이에 밧줄을 연결해서 연결된 나무 사이에는 체력 상관없이 이동할 수 있다.

타잔은 특이한 체질이라서 여러 곳을 이동하더라도 항상 동일한 체력이 유지된다.

타잔이 1번 나무로부터 N번 나무까지 이동하기 위해 필요한 최소의 체력이 얼마인지 구하는 프로그램을 작성하라.

타잔의 체력 timer 1s memory 256MB

타잔의 체력 1s 256MB