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 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.
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.
## 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 ≠ j j-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.
[samples]
**Definitions**
Let $ G = (V, E) $ be an undirected weighted graph with $ n = |V| $ vertices, where $ V = \{1, 2, \dots, n\} $.
Let $ A \in \mathbb{Z}^{n \times n} $ be the adjacency matrix such that:
- $ A_{ii} = 0 $ for all $ i \in V $,
- $ A_{ij} = A_{ji} \in \{ -1 \} \cup [1, 10^6] $ for all $ i \ne j $,
- $ A_{ij} = -1 $ iff $ (i,j) \notin E $,
- $ A_{ij} = w_{ij} \ge 1 $ iff $ (i,j) \in E $ with weight $ w_{ij} $.
**Constraints**
1. $ 1 \le n \le 300 $
2. $ G $ has no self-loops and is symmetric: $ A_{ij} = A_{ji} $
3. Edge weights are positive integers: $ w_{ij} \in [1, 10^6] $
**Objective**
For each vertex $ v \in V $, compute:
$$
c_v = \min \left\{ \sum_{(u,w) \in C} w_{uw} \,\middle|\, C \text{ is a simple cycle containing } v \right\}
$$
If no simple cycle contains $ v $, then $ c_v = -1 $.
Output $ c_1, c_2, \dots, c_n $, one per line.