## Shortest-Paths

Points: 1
Time limit: 4.0s
Memory limit: 1G

Author:
Problem types

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