Üçbucaq marşrut#995
Taksi sürücüsü şəhərdə gedirdi, meydanda sərnişin gördü və yan keçdi. Bir müddət sonra, başqa meydanda, sürücü yenə həmin sərnişini gördü və yenə yan keçdi. Qısa müddətdə, üçüncü meydanda, sürücü yenə bu sərnişini gördü.
- Məndən qaçır! - sərnişin düşündü.
- Üçbucaqdır! - sürücü anladı.
Şəhərdə meydan var. İstənilən iki meydan bir-biri ilə yalnız bir iki istiqamətli yol ilə birləşmişdir. Bu şəhərdə maraqlı vərdişi olan taksi sürücüsü işləyir - bazar günü səhər o qərajdan çıxmağı, taksiyə oturmağı, dəqiq üç meydandan keçən üçbucaq marşrutu seçməyi sevir (yəni, əvvəlcə o hansısa bir meydandan digərinə gedir, sonra - üçüncüsünə, daha sonra isə başlanğıc meydana qayıdır və yenə bu marşrutla gedir). O təsəvvür edir ki, bu yolun haradasa potensial sərnişin gözləyir.
Təbii ki, sürücü təsəvvür etdiyi sərnişinin gözlədiyi yerdən mümkün qədər tez-tez keçmək istəyir. Bunun üçün seçilmiş marşrut mümkün qədər qısa olmalıdır. Taksi sürücüsü üçün optimal marşrut tapan proqram yazın.
İlk sətirdə (3 \leq N \leq 100) ədədi, sonra isə N \times N ölçülü meydanlar arasındakı məsafələr matrisi verilir ( mövqeyindəki ədəd -ci və -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ə -i aşmırlar. Matris əsas diaqonala nisbətən simmetrikdir, əsas diaqonalda yerləşir.
Optimal marşrutdakı meydanların nömrələrini verin. Əgər bir neçə marşrut olarsa, onlardan istənilən birini verin.
Nümunə 1