Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю, стремящийся к бесконечности).
Входные данные
В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.
Выходные данные
Выведите одно число – искомый минимум. Если его не существует, выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
0 42 18468
6335 0 26501
19170 15725 0
|
42 |
| 2 |
3
0 -7 3
-2 0 10
2 215 0
|
-1 |