VIII конкурс по програмиране PC Magazine Bulgaria и Musala Soft Ltd.

---

Вече много години поред зимата изненадва кмета на града г-н Градъо Градски. И този път падна страшно много сняг. А една от фирмите, които г-н Градски по традиция наема, за да чистят снега, “Джаста ООД”, както и друг път е правила, се отказа да чисти. Надеждите на кмета се съсредоточиха изцяло върху втората фирма - “Праста ООД”, която е много зле с техниката и има само един снегорин. Затова г-н Градски се видя в чудо, седи и си блъска главата как да използва оптимално единствения снегорин, за да изчисти N-те кръстовищата на града, номерирани от 1 до N, (3 І N І 300) и свързващите ги M улици. Снегоринът се намира в гаража на фирмата, разположен на кръстовището с номер N. Той трябва да почисти всяка от улиците на града и да се прибере обратно в гаража. За почистване на една улица е достатъчно снегоринът да мине един път по нея. Горивото, което снегоринът ще употреби, е пропорционално на дължината на изминатия път и не зависи от това дали снегоринът се движи по изчистена или по неизчистена улица.
Градоначалникът разполага със списък на улиците на града, представени като двойки от номера на кръстовища, като за всяка улица е зададена и съответната й дължина - цяло положително число, не по-голямо от 1000. Помогнете на градоначалника - напишете програма, която да намери оптималното решение на задачата, та със спестените пари да може да се почисти следващият сняг, който рано или късно пак ще ни изненада.
Входните данни са зададени в текстов файл SNOW.INP, в първия ред на който са само числата N и M, разделени с един интервал. Всеки от следващите M реда на входния файл съдържа номерата на две кръстовища, които са краища на една двупосочна улица и нейната дължина, разделени с по един интервал. Между всеки две кръстовища има не повече от една улица.
Като резултат от работата на програмата изведете в текстов файл SNOW.OUT минималното разстояние, което снегоринът трябва да измине, за да почисти града по зададения начин.

Очакваме решенията на задача 3 не по-късно от 15 януари 2002 г на адрес konkurs@sagabg.net
На сайта www.konkurs.musala.com ще публикуваме съдържанието на задачите от текущия кръг 20 дни преди крайния срок за изпращане на решението, както и всички промени, актуализации, резултати и временното класиране. Там можете да намерите и правилата за участие в нашия конкурс.