Primarul oraşului X doreste să amenajeze în parcul central N locuri pentru picnic, numerotate de la 1 la N, accesul la acestea realizându-se prin intermediul a M alei de lungime cunoscută. Chiar dacă este posibil să nu existe o alee directă, deplasarea de la un loc de picnic la oricare altul este posibilă întotdeauna, trecând prin alte locuri de picnic intermediare. Curăţenia parcului va fi realizată cu ajutorul unei maşini speciale. Pentru a face o economie substanţială de carburant, primarul a stabilit regulile de deplasare pentru maşina de curăţenie, astfel:

• Maşina este garată în locul de picnic numerotat cu 1;
• Maşina trebuie să parcurgă un traseu ce porneste din locul de picnic cu numărul 1, trece de-a lungul fiecărei alei - o dată sau de mai multe ori - şi se reintoarce în punctul de plecare;
• Suma lungimilor aleilor parcurse pe traseu trebuie să fie minimă.

Informaticianul primăriei studiază cerinţa şi, încercând să găsească un traseu care sa treacă o singura data de-a lungul fiecărei alei, işi dă seama că pot exista anumite “puncte de picnic sensibile”, de unde traseul nu mai poate avansa fără a folosi o alee deja parcursă.

Cerinţă

Să se determine lungimea minimă a unui traseu care respectă restricţiile din enunţ.

Date de intrare

Fişierul de intrare picnic.in conţine pe prima linie două numere naturale separate prin spaţiu, N şi M, reprezentând numărul locurilor pentru picnic, respectiv numărul aleilor. Pe fiecare dintre următoarele M linii se află câte un triplet de numere naturale a b c, separate prin câte un spaţiu, cu semnificaţia că există o alee directă ce uneste locurile de picnic a şi b, de lungime c.

Date de ieşire

Fişierul de ieşire picnic.out va conţine o singură linie pe care va fi scris un număr natural reprezentând lungimea minimă a unui traseu care respectă restricţiile din enunţ.

Restricţii

• 1<N<= 1000
• 1<M<=10000
• Lungimile aleilor sunt numere naturale din intervalul [1,500]
• Numărul punctelor de picnic sensibile este cel mult 10.

Exemple

picnic.in	picnic.out	Explicaţii
5 7 1 2 1 2 5 2 1 5 5 1 3 2 3 4 1 4 5 1 2 3 1	16	Un traseu de lungime minimă poate fi: 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1 Aleile (1,2), (3,4) şi (4,5) sunt parcurse de 2 ori fiecare.

prof. Alin Burţa

C. N. "B.P. Hasdeu" Buzău

allbu2003@yahoo.com