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

Se dă un graf orientat 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 arcelor 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. Cerinţă

* $1 ≤ M ≤ N*(N-1)$.
* Nodurile sunt numerotate de la $0$ la $N-1$.
* Costurile arcelor sunt numere întregi cuprinse în intervalul $[1, 1 000 000]$.

* Muchiile grafului sunt distincte două câte două.
* Nu există muchie de la un nod la el însuşi.

h2. Exemplu