17 chairs#4257
Ostap Bender once again tries to recover some valuable jewelry, but this time they are secured in a special box that requires keys to open. By coincidence, each key is hidden in one of chairs, which were sold at a recent auction. After the auction, these chairs were delivered to different cities.
Now Ostap is determined to visit each of the cities to carefully search for and collect each key from the chairs. To avoid unnecessary complications, Ostap does not want to visit any city more than once. He also has a list of travel costs between each pair of cities. Initially, Ostap is in city number , and after collecting all the keys by visiting each city, he can quietly leave the country.
Help Ostap determine the order in which to visit the cities so that he spends as little money as possible on his travels. Perhaps, if you succeed, he will share some of the recovered jewels with you.
The first line contains the number of cities .
Each of the next lines contains non-negative integers. The -th number in the -th line indicates the fare from city to city . If a_{ij} > 0, the fare is a_{ij} rubles; otherwise, it means that direct travel from city to city is impossible.
The number of cities does not exceed the number given in the problem title, and the fare between two cities does not exceed .
In the first line, print the minimum total money needed for Ostap to visit all the cities. On the next line, print numbers—the order in which Ostap should visit the cities to achieve this cost.
If it is impossible for Ostap to collect all the keys while meeting the conditions given in the problem, print a single number .
Example 1
Example 2