Флойд

Задано орієнтований зважений граф. Знайдіть пару вершин, найкоротша відстань від однієї з яких до іншої максимальна серед усіх пар вершин.

Вхідні дані

У першому рядку міститься кількість вершин графа $n(1\le n\le 100)$. У наступних $n$ рядках задано по $n$ чисел, що описують вагову матрицю графа. В ній $-1$ означає відсутність ребра між вершинами, а довільне невід'ємне число — наявність ребра заданої ваги. На головній діагоналі матриці завжди розташовані нулі.

Вихідні дані

Виведіть шукану максимальну найкоротшу відстань.

Приклади