Задачи по информатика:Сняг

Сняг

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

Градоначалникът разполага със списък на улиците на града, представени като двойки от номера на кръстовища, като за всяка улица е зададена и съответната й дължина – цяло положително число, не по-голямо от 1000. Помогнете на градоначалника – напишете програма, която да намери оптималното решение на задачата, та със спестените пари да може да се почисти следващият сняг, който рано или късно пак ще ни изненада.

Входните данни са зададени в текстов файл SNOW.INP, в първия ред на който са само числата N и M, разделени с един интервал. Всеки от следващите M реда на входния файл съдържа номерата на две кръстовища, които са краища на една двупосочна улица и нейната дължина, разделени с по един интервал. Между всеки две кръстовища има не повече от една улица.

Като резултат от работата на програмата изведете в текстов файл SNOW.OUT минималното разстояние което снегоринът трябва да измине за да почисти града по зададения начин. Пример:

SNOW.INP

6 9

1 2 3

1 3 2

1 6 15

2 3 4

2 6 8

4 3 9

5 3 5

5 4 14

6 5 18

SNOW.OUT

93