* 본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제이다.

밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 '커미'는 최근 야근이 잦아져 택시를 더 많이

이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있다. '커미'는 자신이 택시를

이용할 때 동료인 '하니' 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을

알게 되었다. '커미'는 '하니'와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을

얼마나 아낄 수 있을 지 계산해 보고 '하니'에게 합승을 제안해 보려고 한다.

위 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과

예상 요금을 보여주고 있다.

그림에서 커미와 하니 두 사람은 출발지점인 4번 지점에서 출발해서 택시를 타고 귀가 하려고 한다.

커의 집은 6번 지점에 있으며 하니의 집은 2번 지점에 있고 두 사람이 모두 귀가하는 데

소요되는 예상 최저 택시요금이 얼마인지 계산하려고 한다.

* 그림의 []은 지점을 나타내며 [] 안의 숫자는 지점 번호를 나타낸다.

- 지점이 n개일 때, 지점 번호는 1부터 n까지 사용된다.

* 지점 간에 택시가 이동할 수 있는 경로를 간선이라 하며,

간선에 표시된 숫자는 두 지점 사이의 예상 택시요금을 나타낸다.

- 간선은 편의 상 선으로 표시되어 있다.

- 위 그림 예시에서, 4번 지점에서 1번 지점으로(4->1)가거나,

1번 지점에서 4번 지점으로(1->4) 갈 때 예상 택시요금은 10원으로

동일하며 이동 방향에 따라 달라지지 않는다.

* 예상되는 최저 택시요금은 다음과 같이 계산된다.

- 4->1->5 : 커미와 하니가 합승하여 택시를 이용한다.

예상 택시요금은 10 + 24 = 34원이다.

- 5->6 : 커미가 혼자 택시를 이용한다. 예상 택시요금은 2원이다.

- 5->3->2 : 하니가 혼자 택시를 이용한다.

예상 택시요금은 24 + 22 = 46원이다.

- 커미와 하니 모두 귀가 완료까지 예상되는 최저 택시요금은 34+2+46 = 82원이다.

택시합승 timer 1s memory 256MB

택시합승 1s 256MB