14220번 - 양아치 집배원

영선이는 우편을 배달해주는 집배원이다. 이제 n개의 도시를 전부 방문하여 우편물을 배달해야 하는 업무를 받았다. n개의 도시를 중복없이 돌면서 우편물들을 적절히 배달을 해야 하는데, 영선이는 이 일이 너무 귀찮은 나머지 우편물을 대충 배달하기 시작했다.

영선이는 한 도시를 방문할 때마다 우편물을 하나씩 배달한 후 다른 도시로 이동하며(한 도시에서 한번에 여러 우편물을 배달하면 티가 나므로), 빠르게 일을 마칠 수 있다면 잘 못 배달하더라도 방문한 도시를 또 방문하여 잘못된 우편물을 배달한다. 따라서 여러 번 방문한 도시가 존재하고, 방문하지 않은 도시가 발생한다.

결국 영선이의 만행은 들키고 말았고, 당신은 이 우편물들을 다시 회수해야 한다. 하지만 영선이는 출발지도, 어떻게 이동했는지도 까먹었고, 이동한 거리가 최소로 되게 이동했다는 사실만을 알려줬다.

영선이의 이동경로를 파악하기 위해, 전체 이동이 최소가 되는 경로의 이동 거리를 출력하시오.

첫 줄에는 방문하는 도시 n개가 주어지고(1≤n≤500), 그 다음 n줄에는 n개의 원소가 주어지는 데, i번째 줄의 j번째 원소는 i에서 j로 가는데 거리이다. 만약 거리가 0이면 i에서 j로는 이동할 수 없다. 또한, 두 도시를 잇는 도로가 서로 다른 방향에 대해서 거리가 다를 수 있으며, 일방통행인 경우도 존재한다.

거리는 1보다 크며 100,000보다는 작거나 같다.

도시를 n번 방문하는데 최소가 되는 경로의 이동거리를 출력하시오. 만약 최소가 되는 경로를 찾을 수 없으면 -1을 출력하시오.