Scrieti un program care gaseste un traseu de lungime minima in orasul lui Gigel.

h2. Date de intrare

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$.

Pe prima linie din fisierul 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

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.

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

S 1 <= N <= 60
 
S Lungimile strazilor sunt numere naturale din intervalul [1, 10.000]
 
S Daca intre doua intersectii i si j exista o strada, atunci cu singuranta nu va exista o strada intre intersectiile j si i
 
S 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

table(example). |_. traseu.in |_. traseu.out |_. Explicatie |
|6 8
1 2 3

traseu.in traseu.out Explicatie
6 8 28 Traseul ales este:
 
1 2 3 (1,2,3,1,4,6,1,4,5,1)
 

2 3 1

3 1 2

1 4 4

4 6 2

 
4 6 2
 

6 1 5

4 5 1

5 1 6

|28
|Traseul ales este: (1,2,3,1,4,6,1,4,5,1).|

 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/traseu/enunt.files/filelist.xml

==Include(page="template/taskfooter" task_id="traseu")==