İstehza
Ştirliç maşında gedirdi, Bormanın səsini eşitdi və yan keçdi.
Bir müddət sonra o yüksək səsli Bormanı gördü və yenə də yan keçdi. Sonra o Bormanı yenə gördü.
İstehza edir! – Borman düşündü.
Dairəvidir! – Ştirliç anladı.
Şəhərdə N sayda meydan var. İstənilən iki meydan bir-biri ilə yalnız iki istiqamətli bir yol ilə birləşmişdir. Bu şəhərdə Ştirliç yaşayır. Ştirliçin öz məşğuliyyəti var – o bazar günü səhər evdən çıxmağı, maşına oturmağı, hər hansı üç meydandan keçən dairəvi marşrutu seçməyi (yəni, əvvəlcə o hansısa bir meydandan digərinə gedir, sonra – üçüncüsünə, daha sonra isə əvvəlkinə qayıdır və yenə bu marşrutla gedir. O hesab edir ki, haradasa bu yolda Borman dayanmışdır və bu şəkildə bütün bazar günləri Ştirliç başı fırlanmayınca və maşınla gedir və sevinir...
Təbii ki, Ştirliç hesab etdiyi kimi Bormanın daha çox durduğu nöqtədən yan keçmək istəyir. Bunun üçün, təbii ki, Ştirliçin seçdiyi yol kifayət qədər qısa olmalıdır. Ştirliç üçün optimal marşrut seçən proqramı tərtib edin.
Giriş verilənləri
İlk sətirdə əvvəlcə N (3 ≤ N ≤ 100) ədədi, sonra isə NxN ölçülü meydanlar arasındakı məsafələr matrisi verilir. (i, j mövqeyindəki ədəd i-ci və j-ci meydanları birləşdirən yolun uzunluğunu ifadə edir. Matrisdəki bütün ədədlər (əsas diaqonalda yerləşənlərdən başqa) natural ədədlərdir və 1000-i aşmırlar. Matris əsas diaqonala nisbətən simmetrikdir, əsas diaqonalda 0 yerləşir.
Çıxış verilənləri
Optimal marşrutdakı meydanların sayını verin. Əgər bir neçə marşrut olarsa, onlardan istənilən birini verin.