== include(page="template/taskheader" task_id="traseu") ==
==Include(page="template/taskheader" task_id="traseu")==
Poveste ...
Gigel s-a mutat intr-un oras nou! Pentru a se familiariza cu noile imprejurimi a cumparat harta orasului si a observat ca este alcatuita din $M$ strazi de diferite lungimi, cu sens unic si $N$ intersectii de strazi. Gigel a luat harta si a inceput sa alcauiasca un traseu care porneste dintr-o intersectie anume, trece prin fiecare strada cel putin o data, si revine in intersectia de unde a pornit. Desi dorinta lui de explorare este mare, conditia lui fizica nu este tocmai buna, astfel ca vrea sa gasesasca un traseu in care suma lungimilor strazilor parcurse este minima.
h2. Cerinta
...
h2. Restrictii
...
Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.
h2. Date de intrare
...
Pe prima linie a fisierului $traseu.in$ se gasesc numerele $N$ si $M$ separate prin cate un spatiu. Pe urmatoarele $M$ linii se vor gasi triplete de numere $i j k$ cu semnificatia ca exista o strada de la intersectia cu numar $i$ la intersectia cu numar $j$ de lungime $k$.
h2. Date de iesire
...
Pe prima linie din fisierul $traseu.out$ se va afisa un singur numar natural reprezentand lungimea minima a traseului lui Gigel.
h2. Restrictii si precizari
* $1 ≤ N ≤ 60$
* Lungimile strazilor sunt numere naturale din intervalul $[1, 10 000]$
* Daca intre doua intersectii $i$ si $j$ exista o strada, atunci cu singuranta nu va exista o strada si intre intersectiile $j$ si $i$
* Se garanteaza ca exista cel putin un traseu in oras care trece prin fiecare strada cel putin o data si incepe si se termina in aceeasi intersectie
h2. Exemplu
| traseu.in | traseu.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. traseu.in |_. traseu.out |
|6 8
1 2 3
2 3 1
3 1 2
1 4 4
4 6 2
6 1 5
4 5 1
5 1 6
|28 |
h3. Explicatii
== include(page="template/taskfooter" task_id="traseu") ==
Traseul ales este: $(1,2,3,1,4,6,1,4,5,1)$.
==Include(page="template/taskfooter" task_id="traseu")==
