문제

호진이는 이번 방학에 혼자서 해외 여행을 갈 생각이다. 현재 호진이가 사는 나라는 번 나라이고, 가고자 하는 나라는 번 나라이다. 번 나라에서 번 나라로 한 번에 가는 교통편이 있으면 그걸 이용해도 좋지만, 호진이는 최대한 돈을 절약하는 방법으로 번 나라에 가려고 한다.

우선 호진이는 존재하는 모든 교통편의 정보를 찾아보았다. 총 개의 교통편 정보를 찾게 되었는데, 각 교통편의 정보에는 출발하는 나라 와 도착하는 나라 , 그리고 이 교통편을 이용하는 데 소모되는 가격 를 포함되어 있었다. 현재 주어진 정보를 이용하여, 호진이가 번 나라에 도착하기 위한 최소의 비용을 구하여라.

입력

첫째 줄에 정수 이 공백으로 구분되어 주어진다.
이후 개의 줄에 걸쳐서 세 정수 가 주어진다. 이때, 동일한 쌍이 입력으로 여러 번 들어올 수 있다.

출력

호진이가 번 나라로 가기 위한 최소의 비용을 출력한다.

만약 번 나라로 갈 수 없다면 go home을 출력한다.