Трикутний маршрут#995
Водій таксі їхав містом, побачив пасажира, що голосував на площі, і проїхав повз. Через деякий час, на іншій площі, водій знову побачив того ж пасажира, і знову проїхав повз. Незабаром, на третій площі, водій знову побачив цього пасажира.
- Уникає мене! - подумав пасажир.
- Трикутник! - здогадався водій.
У місті площ. Будь-які дві площі з'єднані між собою рівно однією дорогою з двостороннім рухом. У цьому місті працює водій таксі, у якого є цікава звичка - по недільних ранках він любить вийти з гаража, сісти у таксі, вибрати трикутний маршрут, що проходить рівно через три площі (тобто спочатку він їде з якоїсь площі на якусь іншу, потім - на третю, потім повертається на початкову, і знову їде по цьому маршруту). Він уявляє, що десь на цьому шляху чекає потенційний пасажир.
Природно, що водію хочеться проїжджати повз уявне місце очікування пасажира якомога частіше. Для цього обраний маршрут повинен бути якомога коротшим. Напишіть програму, яка знайде оптимальний маршрут для водія таксі.
У першому рядку записано число (3 \leq N \leq 100), а потім матриця N \times N відстаней між площами (число у позиції позначає довжину дороги, яка з'єднує -ту та -ту площі). Всі числа у матриці (крім тих, що стоять на головній діагоналі) - натуральні, не перевищують . Матриця симетрична відносно головної діагоналі, на головній діагоналі стоять .
Виведіть номери площ в оптимальному маршруті. Якщо маршрутів декілька, виведіть будь-який з них.
Приклад 1