D. Пара для мистера Флойда

2000 мс · 256 МБ · всё или ничего

Как классная задача D, но выведите саму пару вершин, между которыми кратчайшее расстояние максимально.

Пар может быть несколько; выведите лексикографически наименьшую по $(i, j)$ . Пары считаются упорядоченными: граф ориентированный, и расстояние из $i$ в $j$ не обязано совпадать с расстоянием из $j$ в $i$ .

Если ни между какой парой различных вершин пути нет, выведите 0 0 0.

Формат ввода

Первая строка содержит число $n$ ( $1 \le n \le 100$ ).

Далее идут $n$ строк по $n$ чисел: $-1$ означает отсутствие ребра. Вес не превосходит $10^4$ , на главной диагонали нули.

Формат вывода

Три числа: $i$ , $j$ и расстояние.

Примеры

ввод

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

вывод

4 6 9

ввод

2
0 -1
-1 0

вывод

0 0 0

Войдите, чтобы отправлять решения.