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

Se dă un {"graf orientat simplu":http://en.wikipedia.org/wiki/Graph_(mathematics)#Simple_graph} 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.

Se dă un {"graf orientat simplu":http://en.wikipedia.org/wiki/Graph_(mathematics)#Simple_graph} cu $N$ vârfuri şi $M$ muchii, fiecare arc 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 arcelor 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.

Fiind dat un graf orientat simplu cu costuri pe arce, să se verifice dacă acesta este hamiltonian. In caz afirmativ, să se determine ciclul hamiltonian de cost minim.

h2. Date de intrare

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

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ă un arc între vârfurile $x$ şi $y$ având costul $c$.

h2. Date de ieşire

* $1 ≤ N ≤ 16$
* $1 ≤ M ≤ N*(N-1)$
* Nodurile sunt numerotate de la $0$ la $N-1$.

* Costurile muchiilor sunt numere întregi cuprinse in intervalul $[1, 1 000 000]$.

* Costurile arcelor sunt numere întregi cuprinse in intervalul $[1, 1 000 000]$.

h2. Exemplu