## Shortest-Paths

No hidden tricks here, read in an adjacency matrix for a positively-weighted and directed graph (no self-edges). Output the shortest distance from \(0\) to each other vertex. Graphs are labelled from \(0\) to \(V\).

#### Input Specification

The first line contains a single integer \(V\), the number of vertices in the graph.

The next \(V\) lines will contain \(V\) space-separated integers specifying an adjacency matrix.

For any element \(v_{i,j}\), a \(0\) indicates no edge from \(u\) to \(v\), a positive value \(c\) indicates there is an edge from \(u\) to \(v\) of cost \(c\).

#### Output Specification

A single line of space-separated integers, the minimum path distance from \(0\) to each vertex in the graph.

If there is no path to a vertex, output \(-1\).

#### Bounds

This problem has three sub-problems, the first is the test data, the second has the following bounds.

- \(1 \leq V \leq 2000\)
- \(v_{i,j} \in \{0,1\}\)

The third has the following bounds

- \(1 \leq V \leq 2000\)
- \(1 \leq v_{i,j} \leq 100\)

#### Sample Input 1

```
4
0 0 0 1
1 0 0 1
1 1 0 0
0 1 0 0
```

#### Sample Output 1

`0 2 -1 1`

#### Sample Input 2

```
5
0 0 0 5 3
0 0 7 4 9
0 0 0 7 0
0 0 0 0 6
9 1 5 10 0
```

#### Sample Output 2

`0 4 8 5 3`

#### Sample Input 3

```
4
0 1 1 1000
0 1 10 100
0 1 1 1
0 0 0 0
```

#### Sample Output 3

`0 1 1 2`

## Comments