Given several directed graphs with *n* vertices,
each one described with a matrix *m* of size *n* × *n*
such that *m*[*i*][*j*] is the cost of going from vertex *i* to vertex *j*,
calculate the minimum cost of the Hamiltonian cycles of every graph.
A Hamiltonian cycle is a path
that visits each vertex exactly once,
and that ends at the starting vertex.

**Input**

Input consists of the description of several graphs.
Each one begins with a natural number *n* ≥ 2,
followed by the matrix *n* × *n* of costs
(*n* lines, each with *n* natural numbers,
with zeroes at the diagonal).

**Output**

Print the minimum cost of the Hamiltonian cycles of every graph.

Public test cases

**Input**

3 0 2 1 2 0 4 1 3 0 4 0 5 7 9 2 0 2 2 2 1 0 3 2 9 9 0

**Output**

6 12

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++