Problem
그의 폐하 부베이 2세는 자신의 영역을 여행하기를 원했습니다. 동시에 경로에는 다음과 같은 소망이 있습니다.
1) 경로는 가능한 최소한의 시간이 소요되어야 합니다(왕실 시간은 매우 귀중한 것이며 보호되어야 함).
2) 경로는 모든 정착지를 정확히 한 번 포함해야 합니다(왕이 정착지를 놓치면 그 주민들은 왕의 부주의에 분노하고 세금 납부를 중단할 것입니다. 정착지 항목도 분개합니다)
3) 경로는 국가의 수도에서 시작하고 끝나야합니다 (왕은 자신의 소유물을 돌아 다니며 즉시 사업을 시작해야합니다). 수도는 경로에 정확히 2번 포함됩니다. 출발지와 목적지로서 경로의 중간 정착지가 될 수 없습니다.
왕국의 로드맵을 사용하여 그러한 경로를 찾거나 모든 요구 사항을 충족하는 것이 불가능하다고 판단하는 프로그램을 작성하십시오.
입력
먼저 숫자 N을 입력합니다(자연, 10을 초과하지 않음) – 왕국의 정착지 수. 그런 다음 각 – 정착지 사이의 이동 시간(시간 –은 음수가 아닌 정수이며 500을 초과하지 않습니다. 시간 = 0이면 일부 정착지 사이에 방법이 없음을 의미합니다). 정착지 1호는 주의 수도입니다.
출판물
폐하가 자신의 영역 주변을 우회하는 데 소요하는 최소 총 시간을 인쇄하거나 주어진 속성으로 경로를 구축할 수 없는 경우 숫자 -1을 인쇄합니다.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |