Повний орієнтований граф заданий матрицею суміжності. (В рядку \(i\) , стопвчику \(j\) міститься відстань від вершини \(i\) до вершини \(j\))
Гарантується, що в графі немає циклів від'ємної ваги.

Знайдіть пару вершин найкоротша відстань між якими максимальна.

Формат вхідних даних

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

Формат вихідних даних

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

Приклад вхідних даних

6
0 6 8 -1 -1 -1
5 0 5 -1 -1 -1
1 7 0 -1 -1 -1
-1 -1 -1 0 6 -1
-1 -1 -1 -1 0 3
-1 -1 -1 2 -1 0

Приклад вихідних даних

9