eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Издевательство

Издевательство

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана. - Издевается! - подумал Борман. - Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

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

Входные данные

В первой строке записано сначала число N (3N100), а затем матрица NxN расстояний между площадями (число в позиции i, j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

Выходные данные

Выведите номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.

Пример

Входные данные #1
5
0  20 10   30 40
20 0  30   1  2
10 30 0    40 1000
30 1  40   0  21
40 2  1000 21 0
Выходные данные #1
4 5 2