A mail carrier needs to deliver letters to multiple places and goes back to the post office to take a rest.
Traveling outside makes him feel tired, so he would like to come up with a shortest path.
Given all distances between every pair of places (including the post office and all destinations), please help the mail carrier figure out the best shortest path, which starts from the post office and ends at the post office.
An additional requirement is that the mail carrier can just go to each place only one time (excluding the starting point, he can go to the start point at the beginning and in the end).
The first line contains an integer N, indicates there are N places (including the post office).
Then there is one N*N martix occupies N lines, with each line contains N integers (>= 0).
ith row jth column = Matrix(i,j) = distance between place i and place j.
The place with index = 0 is the post office.
For all i, j >= 0, Matrix(i,j) = Matrix(j,i), Matrix(i,i) = 0.
N is at most 10 among all test cases.
Print out the minimum distance the mail carrier has to travel to complete his task.
'\n' at the end of output.