진흥국에는 N개의 여행지가 있다.

각 여행사에서는 여행지 사이를 순회하는 셔틀버스를 운행하고 있다.

자유 관광을 하는 K명의 여행자들이 각각 현재 여행지에서 마지막으로 다른 여행지로 이동을 했다가 공항이 있는 N번 여행지로 이동하려고 한다.

그런데 이번이 마지막 여행지라서 반드시 기념품을 파는 가게를 한 곳이라도 들려야 한다.

여행지에는 기념품을 파는 가게가 있지만 모든 여행지마다 가게가 있는 것은 아니다.

공항이 있는 N번 여행지에도 기념품 가게가 있을 수도 있고 없을 수도 있다.

여행지 사이의 정보와 기념품 가게가 있는 여행지가 주어질 때 각 여행자들이 마지막 여행을 마치고 N번 여행지로 이동하기 위해서 지불해야 하는 최소비용을 구하는 프로그램을 작성하라.

마지막 여행지2 timer 1s memory 256MB

마지막 여행지2 1s 256MB