Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.
For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.
Input
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 ≠ jj-th integer in i-th line aij is equal to - 1, then vertices i and j are not connected, otherwise they are connected by the edge of weight aij (1 ≤ aij ≤ 106).
You may assume that graph does not contain self-loops and aij = aji for any 1 ≤ i, j ≤ n.
Output
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.