F. Кратчайшие циклы
ограничение по времени на тест
4 секунды (5 секунд для Java)
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный взвешенный граф. Для каждой вершины найдите длину кратчайшего простого цикла, проходящего через данную вершину.

Входные данные

Первая строка содержит целое число n — количество вершин (1 ≤ n ≤ 300).

В следующих n строках находится по n целых чисел, которые задают матрицу смежности. j-ое число в i строке задает число aij — вес ребра, соединяющего вершины i и j. Если aij равно  - 1, то это означает, что между i и j ребра нет. Матрица симметрична, т.е. aij = aji для любых 1 ≤ i, j ≤ n. Для всех 1 ≤ i ≤ n aii = 0, при этом петель граф не содержит.

Все ребра имеют вес от 1 до 106.

Выходные данные

Выведите n строк, каждая из которых содержит одно целое число. i-ое из этих чисел должно быть равно длине кратчайшего простого цикла, проходящего через вершину i. Если через вершину i не проходит ни одного простого цикла — выводите  - 1.

Примеры
Входные данные
4
0 9 1 1
9 0 -1 1
1 -1 0 -1
1 1 -1 0
Выходные данные
11
11
-1
11