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