traseu

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 y_1,…,y_k, k>2. Strada y_i (1<=i<=k) leaga intersectiile x_i si x_(i+1), iar strada y_k conecteaza intersectiile x_k si x_1. Toate numerele de ordine ale intersectiilor prin care se trece (x_1,…,x_k) sunt diferite doua cate doua. Lungimea unui traseu este egala cu suma lungimilor strazilor din care este alcatuit, adica L(y_1)+L(y_2)+…+L(y_k) unde L(y_I) este lungimea strazii y_i (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 2 intregi N<=100 reprezentand numarul de intersectii si M<=10000 reprezentand numarul de strazi. Pe urmatoarele M linii se afla descrierilor strazilor, cate una pe linie. Fiecare linie contine 3 intregi: numarul de ordine al intersectiilor unite de strada si lungimea strazii (care este un intreg mai mic decat 500).

 

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

Exemplu

traseu.in

traseu.in
(o iesire posibila)

5 7

1 4 1

1 3 300

3 1 10

1 2 16

2 3 100

2 5 15

5 3 20

1 3 5 2

 

traseu.in

traseu.in
(singura iesire posibila)

4 3

1 2 10

1 3 20

1 4 30

0

 

Timp maxim de executie/test: 0.2 secunde

Daniel Dumitran

Student la Universitatea Politehnica Bucuresti

Contact:odumitran@go.ro