Minimum Travel Time

You are given n landmarks and an n × n matrix representing the travel times between each pair of landmarks. The task is to determine the minimum travel time required to start at landmark 0, visit all other landmarks exactly once, and return to the starting point. If it is impossible to complete the tour due to unreachable paths, output -1.

The travel time between two landmarks is given as an integer. In the input, if a travel time is represented by -1, it means that there is no direct path between those two landmarks.

Note: All formulas below must be written in LaTeX format. For example, the total travel time for a given permutation \(p\) is:

\(T = t_{0,p_1} + \sum_{i=1}^{n-2} t_{p_i, p_{i+1}} + t_{p_{n-1},0}\)

inputFormat

The input is read from stdin and contains:

• An integer \(n\) on the first line, representing the number of landmarks.
• \(n\) lines follow, each with \(n\) space-separated integers. The \(j\)th number in the \(i\)th line denotes the travel time from landmark \(i\) to landmark \(j\). A value of -1 indicates that the path is not available. Note that the diagonal entries will always be 0.

outputFormat

Output a single integer to stdout that represents the minimum travel time required to visit all landmarks and return to the starting point. If it is impossible, output -1.

## sample

1
0

0

</p>