== include(page="template/taskheader" task_id="hamilton") ==

Poveste şi cerinţă...

Se dă un "graf neorientat simplu":http://en.wikipedia.org/wiki/Simple_graph#Simple_graphsim cu $N$ vârfuri şi $M$ muchii, fiecare muchie având asociat un cost. Un ciclu al acestui graf se numeşte hamiltonian dacă conţine fiecare nod din graf exact o singură dată. Un graf care conţine un astfel de ciclu se numeşte graf hamiltonian. Costul unui ciclu este egal cu suma muchiilor aflate pe ciclu.
 
h3. Cerinta
 
Fiind dat un graf neorientat simplu cu costuri pe muchii, să se verifice dacă acesta este hamiltonian. In caz afirmativ, să se determine ciclul hamiltonian de cost minim.

h2. Date de intrare

Fişierul de intrare $hamilton.in$ ...

Pe prima linie a fişierului de intrare $hamilton.in$ se afla două numere întregi $N$ si $M$. Pe fiecare din următoarele $M$ linii se găseşte un triplet de forma $x y c$ cu semnificaţia că există muchie între vârfurile $x$ şi $y$ având costul $c$.

h2. Date de ieşire

În fişierul de ieşire $hamilton.out$ ...

Pe prima linie a fişierului de ieşire $hamilton.out$ se va afla costul ciclului cerut. Următoarea linie va conţine $N$ numere $x{~1~} x{~2~} ... x{~n~}$ cu proprietatea că $(x{~1~} x{~2~}) (x{~2~} x{~3~}) ... (x{~N-1~} x{~N~}) (x{~N~} x{~1~})$ reprezintă un ciclu hamiltonian de cost minim. În cazul în care graful nu este hamiltonian, atunci în fişierul de ieşire se va afişa $-1$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 16$
* $1 ≤ M ≤ N*(N-1)/2$
* Costurile muchiilor sunt numere întregi cuprinse in intervalul $[1, 1 000 000]$.

h2. Exemplu