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.