402839: GYM100917 F Find the Length

For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.

First line of the input contains one inteter n — number of vertices in the graph (1 ≤ n ≤ 300).

Each of n lines contain n integers, i-th integer in the i-th column is equal to 0 for any i. If for i ≠ j j-th integer in i-th line a_ij is equal to  - 1, then vertices i and j are not connected, otherwise they are connected by the edge of weight a_ij (1 ≤ a_ij ≤ 10⁶).

You may assume that graph does not contain self-loops and a_ij = a_ji for any 1 ≤ i, j ≤ n.

Print n integers one per line. i-th of those integers must be lentgh of the shortest simple cycle, containig i-th vertice. If no simple cycles contain i-th vertiex, print  - 1 at corresponding line.

4
0 9 1 1
9 0 -1 1
1 -1 0 -1
1 1 -1 0

11
11
-1
11