Shortest Path in Checkpoints Race

You are given an \(n \times n\) matrix \(D\) where \(D[i][j]\) represents the distance from checkpoint \(i\) to checkpoint \(j\). A value of \(-1\) indicates that there is no direct route between checkpoints.

The race begins at checkpoint 0 and ends at checkpoint \(n-1\). Your task is to find the minimum total distance required to travel from checkpoint 0 to checkpoint \(n-1\). If no valid path exists, output \(-1\).

Formally, if there exists a path \(P = 0 \rightarrow i_1 \rightarrow \cdots \rightarrow n-1\) such that each edge from \(u\) to \(v\) exists (i.e. \(D[u][v] \neq -1\)), you are to compute the value:

[ \min_{P}\sum_{(u,v) \in P} D[u][v] ]

Otherwise, output \(-1\).

For example, given the matrix:

3
0 1 -1
-1 0 2
1 -1 0

the shortest path distance is 3.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(n\) representing the number of checkpoints.
• The following \(n\) lines each contain \(n\) space-separated integers. The \(j^{th}\) integer on the \(i^{th}\) line is \(D[i][j]\), the distance from checkpoint \(i\) to checkpoint \(j\). A distance of \(-1\) means that there is no direct path.

outputFormat

Output a single integer to stdout which represents the shortest distance from checkpoint 0 to checkpoint \(n-1\). If there is no valid path, output \(-1\).

## sample

3
0 1 -1
-1 0 2
1 -1 0

3