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

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

Формат входных данных
В первой строке входного файла единственное число 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