Ostap Bender again tries to get the jewelry, but this time they were banned in a box for opening which you must have n keys. By coincidence, each of the keys was hidden in one of the n chairs sold out at a recent auction. After the auction, these chairs were delivered to n cities.

And now Ostap decided on a new crazy idea: to stop by each of the cities and, having turned a scam in each of them, steal the necessary keys. To avoid conflicts with ill-wishers, Ostap does not want to appear in any city more than once. Ostap also has a list of prices for travel between each pair of cities. Initially, Ostap is located in the city number 1 and after visiting all the cities, he can quietly hide from this country.

Help Ostap to find the order of visiting cities so that he will spend as little money as possible on wanderings, and then, perhaps, he will share the diamonds mined with you.

Input

The first line contains the number of cities n. Each of the next n lines contains n non-negative integers. j - th number in the i - th line means the fare from the city i to the city j. If aij > 0, then the fare is aij rubles, otherwise it means that it is impossible to drive directly from city i to city j.

The number of cities does not exceed the number mentioned in the title of the problem, and the fare between two cities does not exceed 100.

Output

In the first line print the minimum amount of money needed to visit all the cities by Ostap. On the next line print n numbers - the order of visiting cities, in which this sum is reached.

If Ostap fails to get all the keys while meeting the conditions specified in the problem statement, then print a single number -1.