# Hamiltonian paths P56416

Statement

thehtml

Given a directed graph with arcs with positive costs, print all the paths that begin at the first vertex and visit all vertices exactly once. Moreover, compute the minimum of the costs of these paths.

Input

Input consists of the number of vertices n, followed by n rows with n natural numbers each. The j-th number of the i-th row indicates the cost of the arc going from vertex i to vertex j. A zero cost indicates a missing arc (the diagonal has only zeros). Assume 2 ≤ n ≤ 15, and that all costs are between 1 and 106.

Output

Print, in lexicographical order, print all the paths that begin at the first vertex and visit all vertices exactly once. Afterwards, print the minimum cost of all these paths. There will always be at least one path.

Public test cases
• Input

```3
0 7 3
9 0 2
9 8 0
```

Output

```1 2 3
1 3 2
min: 9
```
• Input

```2
0 1000000
1 0
```

Output

```1 2
min: 1000000
```
• Input

```5
0 2 0 2 1
0 0 2 0 2
0 1 0 2 2
0 2 1 0 2
0 0 2 1 0
```

Output

```1 2 3 4 5
1 2 3 5 4
1 2 5 3 4
1 2 5 4 3
1 4 2 3 5
1 4 2 5 3
1 4 3 2 5
1 4 5 3 2
1 5 3 4 2
1 5 4 2 3
1 5 4 3 2
min: 4
```
• Information
Author