17 stul#4257
Ostap Bender bir daha qiymətli zinət əşyalarını tapmağa çalışır, lakin bu dəfə onlar yalnız açarla açılan xüsusi bir qutuda qorunur. Təsadüfən, hər bir açar stuldan birində gizlədilib və bu stullar sonuncu hərracda satılıb. Hərracdan sonra həmin stullar müxtəlif şəhərə göndərilib.
İndi Ostap hər bir şəhəri ziyarət edib, stulları diqqətlə axtararaq açarları toplamağa qərarlıdır. Lazımsız çətinliklərdən qaçmaq üçün Ostap heç bir şəhərə iki dəfə getmək istəmir. O, həmçinin hər bir şəhər cütü arasında səfər xərclərinin siyahısına malikdir. Əvvəlcə Ostap -ci şəhərdədir və bütün açarları yığdıqdan sonra ölkəni sakitcə tərk edə bilər.
Ostapa şəhərləri hansı ardıcıllıqla gəzəcəyini müəyyənləşdirməkdə kömək et ki, səfərə mümkün qədər az pul sərf etsin. Bəlkə də, bacarsan, o, tapılan zinət əşyalarının bir hissəsini səninlə bölüşər.
Birinci sətrdə şəhərin sayı verilir.
Sonrakı sətrin hər birində qeyri-mənfi tam ədəd var. -ci sətrin -ci ədədi -ci şəhərdən -ci şəhərə yol haqqını göstərir. Əgər a_{ij} > 0 olarsa, yol haqqı a_{ij} rubl olur; əks halda, bu, -ci şəhərdən -ci şəhərə birbaşa səfərin mümkün olmadığını bildirir.
Şəhərlərin sayı məsələnin başlığında verilmiş ədəddən çox deyil, iki şəhər arasındakı yol haqqı isə -dən böyük deyil.
Birinci sətrdə Ostapın bütün şəhərləri ziyarət etmək üçün lazım olan minimal ümumi məbləği çap edin. Növbəti sətrdə isə bu xərclə nail olmaq üçün Ostapın şəhərləri hansı ardıcıllıqla gəzməli olduğunu göstərən ədədi—şəhərlərin ardıcıllığını çap edin.
Əgər göstərilən şərtlərlə Ostapın bütün açarları toplaması mümkün deyilsə, yeganə bir çap edin.
Nümunə 1
Nümunə 2