Задача "Две наиболее удаленные вершины"

Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.

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

Формат выходных данных
Вывести искомое максимальное кратчайшее расстояние.

Пример

Пример ввода Пример вывода
4
0 5 9 -1
-1 0 2 8
-1 -1 0 7
4 -1 -1 0
16