In orasul Adelton din insula Zanzibar exista o agentie de turism. Agentia
a decis sa ofere clientilor ei vizite la diferite obiective turistice. Pentru
a castiga cat mai multi bani, agentia a luat urmatoarea decizie: este necesara
gasirea unui drum de lungime minima care incepe si se termina in acelasi loc.
In oras sunt N intersectii numerotate de la 1 la N si M strazi bidirectionale.
Doua intersectii pot fi unite prin mai multe strazi, dar nu exista nici o
strada care are ambele extremitati in aceeasi intersectie. Orice traseu este
o secventa de strazi y1,…,yk, k>2. Strada yi (1<=i<=k) leaga intersectiile
xi si xi+1, iar strada yk conecteaza intersectiile xk si x1. Toate
numerele de ordine ale intersectiilor prin care se trece (x1,…,xk) sunt
diferite doua cate doua. Lungimea unui traseu este egala cu suma lungimilor
strazilor din care este alcatuit, adica L(y1)+L(y2)+…+L(yk) unde L(yi) este lungimea strazii yi (1<=i<=k).
Cerinta
Scrieti un program care gaseste un traseu de lungime
minima. In cazul in care nu exista nici un traseu programul va afisa 0
Date de intrare
Datele se citesc din fisierul traseu.in.
Pe prima linie se afla doi intregi N, reprezentand numarul de intersectii
si M reprezentand numarul de strazi. Pe urmatoarele M linii se afla
descrierilor strazilor, cate una pe linie. Fiecare linie contine trei intregi:
numarul de ordine al intersectiilor unite de strada si lungimea strazii.
Date de iesire
Datele de iesire se scriu in fisierul traseu.out.
Acest fisier contine o lingura linie. Aceasta linie poate contine fie 0,
fie o insiruire a numerelor de ordine ale intersectiilor din care este alcatuit
traseul. Fiecare intersectie trebuie sa apara o singura data (prima intersectie
nu se va scrie si la sfarsit).
Restrictii si observatii
N <= 100
M <= 10000
Lungimile strazilor sunt numere naturale mai mici decat 500
Daca exista mai multe solutii se cere una singura.