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