Бодлого F. Такси

Бодолт илгээх

Миша ах сургууль дээрээс нь Кирилл, Илья, Паша, Олег нарыг гэрт нь машинаараа хүргэж өгөөд өөрөө гэртээ харих гэж байгаа. Паша Олег хоёр ойрхон амьдардаг, Илья хамгийн сүүлд гэртээ хүргүүлэхийг хүсэхгүй байгаа. Газрын зураг дээр сургууль (1), Кириллийн (2), Ильягийн (3), Паша болон Олег нарын гэр (4), Миша ахын гэрийг(5) тэмдэглэсэн. (1)-ээс гараад (5) дээр дуусах хамгийн богино замыг ол. (3) цэг нь сүүлийн цэгийн өмнөх байж болохгүй.

Оролт

Цэгүүдийн хоорондох зайн массив өгөгдөнө. Уг массив таван мөр, таван баганатай. i-р мөрийн j-р баганын тоо нь i-р болон j-р цэгүүдийн хоорондох зай юм(1 ≤ i, j ≤ 5). Бүх зай нь метрээр өгөгдөх ба сөрөг биш бүхэл тоо байна. Мөн тэдгээр нь 10000-аас хэтрэхгүй. Ямар ч цэгээс уг цэг хүртлэх зай нь тэгтэй тэнцүү, ямар ч хоёр цэгийн хооронд аль ч чиглэлд явсан ижил зайтай байна. Мөн ямар ч хоёр цэгийн хооронд шууд явах зай нь гуравдагч цэгээр дамжин явах зайнаасаа их биш байна.

Гаралт

Хоёр мөр мэдээлэл гаргана.
Эхний мөрөнд хамгийн оновчтой замын нийт урт байна.
Хоёр дахь мөрөнд цэгүүдийг дайрч өнгөрөх дараалал болох таван бүхэл тоо байна. Хэрэв бодлого олон зөв шийдтэй бол аль нэгийг нь гаргана.

Жишээ оролт

0 2600 3800 2600 2500
2600 0 5300 3900 4400
3800 5300 0 1900 4500
2600 3900 1900 0 3700
2500 4400 4500 3700 0

Жишээ гаралт

13500
1 2 3 4 5