양아치 집배원

영선이는 우편을 배달하는 집배원이다. 이번에는 도시 $n$개를 돌며 우편물을 배달하는 일을 맡았다. 그런데 일이 너무 귀찮은 나머지 우편물을 대충 배달하기 시작했다.

영선이는 도시에 도착하면 우편물을 하나만 놓고 곧바로 다른 도시로 떠난다. 한 도시에 여러 개를 한꺼번에 놓으면 티가 나기 때문이다. 대신 빨리 끝낼 수만 있다면 이미 들렀던 도시에 또 들러 엉뚱한 우편물을 놓는다. 그래서 여러 번 방문한 도시가 생기고, 한 번도 방문하지 않은 도시도 생긴다.

결국 영선이의 만행이 들통났고, 당신이 우편물을 회수하게 됐다. 영선이는 출발한 도시도 이동한 순서도 기억하지 못한다. 이동 거리의 합이 최소가 되도록 움직였다는 사실만 알려줬다.

영선이는 도시를 정확히 $n$번 방문했다. 즉 어떤 도시에서 출발해 $n-1$번 이동했고, 같은 도시를 여러 번 방문해도 된다. 이런 경로의 이동 거리 합 중 최솟값을 구하라.

첫 줄에 도시의 수 $n$이 주어진다 ($1 \le n \le 500$). 다음 $n$개 줄에는 각각 정수 $n$개가 주어지며, $i$번째 줄의 $j$번째 정수는 도시 $i$에서 도시 $j$로 가는 도로의 길이다. 이 값이 0이면 $i$에서 $j$로 가는 도로가 없다는 뜻이고, 대각선 원소는 항상 0이다. 도로의 길이는 1 이상 100,000 이하이다. 두 도시를 잇는 도로는 방향에 따라 길이가 다를 수 있고, 한쪽 방향으로만 나 있기도 하다.

도시를 $n$번 방문하는 경로 중 이동 거리의 합이 가장 작은 값을 출력한다. 그런 경로가 없으면 -1을 출력한다.