The Lazy Postman

Yeongseon is a postman. His new job is to deliver mail across $n$ cities. The work bores him, so he starts delivering carelessly.

Whenever Yeongseon reaches a city he drops exactly one piece of mail and leaves for another city at once, because dropping several pieces in the same city would give him away. If it gets him done sooner he goes back to a city he already visited and drops the wrong mail there. Some cities end up visited many times and some are never visited.

His trick was found out, and you have to collect the mail again. Yeongseon does not remember which city he started from or in what order he moved. He only told you that he moved so that the total distance was as small as possible.

Yeongseon visited a city exactly $n$ times, so he started somewhere and moved $n-1$ times, and the same city may be visited more than once. Find the smallest total distance of such a route.

The first line has the number of cities $n$ ($1 \le n \le 500$). Each of the next $n$ lines has $n$ integers. The $j$-th integer on the $i$-th line is the length of the road from city $i$ to city $j$. A value of 0 means there is no road from $i$ to $j$, and the diagonal entries are always 0. Every road length is between 1 and 100,000. The two directions between a pair of cities may have different lengths, and some roads run one way only.

Print the smallest total distance over all routes that visit a city $n$ times. If no such route exists, print -1.