// Problem komiwojażera
// Data: 22.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program TSProblem;

// Typy dla dynamicznej
// macierzy sąsiedztwa
type
  // Wiersz tablicy sąsiedztwa
  nptr = array of boolean;
  // Wiersz macierzy wag krawędzi
  wnptr = array of integer;

// Zmienne globalne
var
  n,m,v0,d,dh,sptr,shptr : integer;
  // Macierz sąsiedztwa
  A : array of nptr;
  // Macierz wag
  W : array of wnptr;
  // Stosy w tablicy
  S, Sh : array of integer;
  // Tablica odwiedzin
  vs : array of boolean;

// Rekurencyjna procedura
// poszukiwania cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
// v - wierzchołek bieżący
//----------------------------------
procedure TSP(v : integer);
var
  u : integer;
begin
  // zapamiętujemy na stosie
  // bieżący wierzchołek
  Sh[shptr] := v;
  inc(shptr);
  // jeśli brak ścieżki Hamiltona,
  // to jej szukamy
  if shptr < n then
  begin
    // Oznaczamy bieżący wierzchołek
    // jako odwiedzony
    vs[v] := true;
    // Przeglądamy sąsiadów
    // wierzchołka v
    for u := 0 to n-1 do
      // Szukamy nieodwiedzonego
      // jeszcze sąsiada
      if A[v][u] and not vs[u] then
      begin
        // Dodajemy wagę krawędzi
        // v - u do sumy
        inc(dh, W[v][u]);
        // Rekurencyjnie wywołujemy
        // szukanie cyklu Hamiltona
        TSP(u);
        // Usuwamy wagę krawędzi
        // z sumy
        dec(dh, W[v][u]);
      end;
    // Zwalniamy bieżący wierzchołek
    vs[v] := false;
  end
  // Jeśli znaleziona ścieżka
  // jest cyklem Hamiltona,
  else if A[v0][v] then
  begin
    // to sprawdzamy,
    // czy ma najmniejszą sumę wag
    inc(dh, W[v][v0]);
    // Jeśli tak,
    if dh < d then
    begin
      // To zapamiętujemy tę sumę
      d := dh;
      // oraz kopiujemy stos Sh do S
      for u := 0 to shptr-1 do
        S[u] := Sh[u];
      sptr := shptr;
    end;
    // Usuwamy wagę krawędzi
    // v - v0 z sumy
    dec(dh, W[v][v0]);
  end;
  // Usuwamy bieżący
  // wierzchołek ze ścieżki
  dec(shptr);
end;

//**********************
//*** Program główny ***
//**********************

var
  i, j, x, y, z : integer;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy struktury
  // dynamiczne i inicjujemy je
  SetLength(S, n);
  SetLength(Sh, n);
  SetLength(vs, n);
  SetLength(A, n);
  SetLength(W, n);
  for i := 0 to n-1 do
  begin
    SetLength(A[i], n);
    SetLength(W[i], n);
    for j := 0 to n-1 do
    begin
      A[i][j] := false;
      W[i][j] := 0;
    end;
    vs[i] := false;
  end;
  sptr := 0;
  shptr := 0;
  // Odczytujemy dane wejściowe
  for i := 0 to m-1 do
  begin
    read(x, y, z);
    // Krawędź x - y
    A[x][y] := true;
    A[y][x] := true;
    // Waga krawędzi x - y
    W[x][y] := z;
    W[y][x] := z;
  end;
  writeln;
  // Rozpoczynamy algorytm
  d  := MAXINT;
  dh := 0;
  v0 := 0;
  TSP(v0);
  if sptr > 0 then
  begin
    for i := 0 to sptr-1 do
      write(S[i], ' ');
    writeln(v0);
    writeln('d = ', d);
  end
  else
    writeln('NO HAMILTONIAN CYCLE');
  writeln;
  // Usuwamy tablice dynamiczne
  SetLength(S, 0);
  SetLength(Sh, 0);
  SetLength(vs, 0);
  for i := 0 to n-1 do
  begin
    SetLength(A[i], 0);
    SetLength(W[i], 0);
  end;
  SetLength(A, 0);
  SetLength(W, 0);
end.

// Problem komiwojażera
// Data: 22.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Zmienne globalne
int n,m,v0,d,dh,sptr,shptr;
// Macierz sąsiedztwa
bool **A;
// Macierz wag krawędzi
int **W;
// Stosy w tablicy
int *S, *Sh;
// Tablica odwiedzin
bool *vs;

// Rekurencyjna procedura
// poszukiwania cyklu Hamiltona
// o najmniejszej sumie
// wag krawędzi
// v - wierzchołek bieżący
//-----------------------------
void TSP(int v)
{
  int u;
  // zapamiętujemy na stosie
  // bieżący wierzchołek
  Sh[shptr++] = v;
  // jeśli brak ścieżki
  // Hamiltona, to jej szukamy
  if(shptr < n)
  {
    // Oznaczamy bieżący
    // wierzchołek
    // jako odwiedzony
    vs[v] = true;
    // Przeglądamy sąsiadów
    // wierzchołka v
    for(u = 0; u < n; u++)
      // Szukamy nieodwiedzonego
      // jeszcze sąsiada
      if(A[v][u] && !vs[u])
      {
        // Dodajemy wagę
        // krawędzi v - u do sumy
        dh += W[v][u];
        // Rekurencyjnie
        // wywołujemy szukanie
        // cyklu Hamiltona
        TSP(u);
        // Usuwamy wagę
        // krawędzi z sumy
        dh -= W[v][u];
      }
    // Zwalniamy
    // bieżący wierzchołek
    vs[v] = false;
  }
  // Jeśli znaleziona ścieżka
  // jest cyklem Hamiltona,
  else if(A[v0][v])
  {
    // to sprawdzamy,
    // czy ma najmniejszą
    // sumę wag
    dh += W[v][v0];
    // Jeśli tak,
    if(dh < d)
    {
      // to zapamiętujemy tę sumę
      d = dh;
      // oraz kopiujemy
      // stos Sh do S
      for(u = 0; u < shptr; u++)
        S[u] = Sh[u];
      sptr = shptr;
    }
    // Usuwamy wagę krawędzi
    // v - v0 z sumy
    dh -= W[v][v0];
  }
  // Usuwamy bieżący
  // wierzchołek ze ścieżki
  shptr--;
}

//**********************
//*** Program główny ***
//**********************

int main()
{
  int i, j, x, y, z;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy struktury
  // dynamiczne i inicjujemy je
  S  = new int [n];
  Sh = new int [n];
  vs = new bool [n];
  A  = new bool * [n];
  W  = new int * [n];
  for(i = 0; i < n; i++)
  {
    A[i] = new bool [n];
    W[i] = new int [n];
    for(j = 0; j < n; j++)
    {
      A[i][j] = false;
      W[i][j] = 0;
    }
    vs[i] = false;
  }
  sptr = shptr = 0;

  // Odczytujemy dane wejściowe
  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> z;
    // Krawędź x - y
    A[x][y] = A[y][x] = true;
    // Waga krawędzi x - y
    W[x][y] = W[y][x] = z;
  }
  cout << endl;
  // Rozpoczynamy algorytm
  d  = MAXINT;
  dh = v0 = 0;
  TSP(v0);
  if(sptr)
  {
    for(i = 0; i < sptr; i++)
      cout << S[i] << " ";
    cout << v0 << endl;
    cout << "d = " << d << endl;
  }
  else
    cout << "NO HAMILTONIAN CYCLE"
         << endl;
  cout << endl;
  // Usuwamy tablice dynamiczne
  delete [] S;
  delete [] Sh;
  delete [] vs;
  for(i = 0; i < n; i++)
  {
    delete [] A[i];
    delete [] W[i];
  }
  delete [] A;
  delete [] W;
  return 0;
}

' Problem komiwojażera
' Data: 22.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

Const MAXINT = 2147483647

' Zmienne globalne

Dim Shared As Integer n,m,v0,d
Dim Shared As Integer dhx,sptr,shptr
' Macierz sąsiedztwa
Dim Shared As Byte Ptr Ptr A
' Macierz wag krawędzi
Dim Shared As Integer Ptr Ptr W
' Stosy w tablicy
Dim Shared As Integer Ptr S, Sh
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' Rekurencyjna procedura
' poszukiwania cyklu Hamiltona
' o najmniejszej sumie wag krawędzi
' v - wierzchołek bieżący
'----------------------------------
Sub TSP (ByVal v As Integer)
  Dim As Integer u

  ' zapamiętujemy na stosie
  ' bieżący wierzchołek
  Sh[shptr] = v
  shptr += 1
  ' jeśli brak ścieżki Hamiltona,
  ' to jej szukamy
  If shptr < n Then
    ' Oznaczamy bieżący
    ' wierzchołek jako odwiedzony
    vs[v] = 1
    ' Przeglądamy sąsiadów
    ' wierzchołka v
    For u = 0 To n-1
      ' Szukamy nieodwiedzonego
      ' jeszcze sąsiada
      If (A[v][u] = 1) AndAlso _
         (vs[u] = 0) Then
        ' Dodajemy wagę
        ' krawędzi v - u do sumy
        dhx += W[v][u]
        ' Rekurencyjnie wywołujemy
        ' szukanie cyklu Hamiltona
        TSP(u)
        ' Usuwamy wagę
        ' krawędzi z sumy
        dhx -= W[v][u]
      End If
    Next
    ' Zwalniamy bieżący wierzchołek
    vs[v] = 0
  ' Jeśli znaleziona ścieżka
  ' jest cyklem Hamiltona,
  ElseIf A[v0][v] = 1 Then
    ' to sprawdzamy,
    ' czy ma najmniejszą sumę wag
    dhx += W[v][v0]
    ' Jeśli tak, 
    If dhx < d Then
      ' To zapamiętujemy tę sumę
      d = dhx
      ' oraz kopiujemy stos Sh do S
      For u = 0 To shptr-1
        S[u] = Sh[u]
      Next
      sptr = shptr
    End If
    ' Usuwamy wagę krawędzi
    ' v - v0 z sumy
    dhx -= W[v][v0]
  End If
  ' Usuwamy bieżący
  ' wierzchołek ze ścieżki
  shptr -= 1
End Sub

'**********************
'*** Program główny ***
'**********************

Dim as Integer i, j, x, y, z

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy struktury
' dynamiczne i inicjujemy je
S  = New Integer [n]
Sh = New Integer [n]
vs = New Byte [n]
A  = New Byte Ptr [n]
W  = New Integer Ptr [n]
For i = 0 To n-1
  A[i] = New Byte [n]
  W[i] = New Integer [n]
  For j = 0 To n-1
    A[i][j] = 0
    W[i][j] = 0
  Next
  vs[i] = 0
Next
sptr  = 0
shptr = 0
' Odczytujemy dane wejściowe
For i = 0 To m-1
  Input #1, x, y, z
  ' Krawędź x-y
  A[x][y] = 1
  A[y][x] = 1
  ' Waga krawędzi x-y
  W[x][y] = z
  W[y][x] = z
Next
Close #1
Print
' Rozpoczynamy algorytm
d  = MAXINT
dhx = 0
v0 = 0
TSP(v0)
If sptr > 0 Then
  For i = 0 To sptr-1
  	 Print S[i];
  Next
  Print v0
  Print " d =";d
Else
  Print "NO HAMILTONIAN CYCLE"
End If
Print
' Usuwamy tablice dynamiczne
Delete [] S
Delete [] Sh
Delete [] vs
For i = 0 To n-1
  Delete [] A[i]
  Delete [] W[i]
Next
Delete [] A
Delete [] W
End

# Problem komiwojażera
# Data: 7.03.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647

# Rekurencyjna procedura
# poszukiwania cyklu Hamiltona
# o najmniejszej sumie wag krawędzi
# v - wierzchołek bieżący
#----------------------------------
def tsp(v):
    global s,sh,shptr,sptr,n,m,vs,a,dhx,w,v0,d
    # zapamiętujemy na stosie
    # bieżący wierzchołek
    sh[shptr] = v
    shptr += 1
    # jeśli brak ścieżki Hamiltona,
    # to jej szukamy
    if shptr < n:
        # Oznaczamy bieżący
        # wierzchołek jako odwiedzony
        vs[v] = True
        # Przeglądamy sąsiadów
        # wierzchołka v
        for u in range(n):
            # Szukamy nieodwiedzonego
            # jeszcze sąsiada
            if a[v][u] and not vs[u]:
                # Dodajemy wagę
                # krawędzi v - u do sumy
                dhx += w[v][u]
                # Rekurencyjnie wywołujemy
                # szukanie cyklu Hamiltona
                tsp(u)
                # Usuwamy wagę
                # krawędzi z sumy
                dhx -= w[v][u]
        # Zwalniamy bieżący wierzchołek
        vs[v] = False
    # Jeśli znaleziona ścieżka
    # jest cyklem Hamiltona,
    elif a[v0][v]:
        # to sprawdzamy,
        # czy ma najmniejszą sumę wag
        dhx += w[v][v0]
        # Jeśli tak, 
        if dhx < d:
            # To zapamiętujemy tę sumę
            d = dhx
            # oraz kopiujemy stos Sh do S
            for u in range(shptr):
                s[u] = sh[u]
            sptr = shptr
        # Usuwamy wagę krawędzi
        # v - v0 z sumy
        dhx -= w[v][v0]
    # Usuwamy bieżący
    # wierzchołek ze ścieżki
    shptr -= 1

#**********************
#*** Program główny ***
#**********************

# Czytamy liczbę
# wierzchołków i krawędzi
q = input().split()
n = int(q[0])
m = int(q[1])
# Tworzymy struktury
# dynamiczne i inicjujemy je
s  = [0] * n
sh = [0] * n
vs = [False] * n
a = []
w = []
for i in range(n):
    q = [False] * n
    r = [0] * n
    a.append(q)
    w.append(r)
    del q,r
sptr  = 0
shptr = 0
# Odczytujemy dane wejściowe
for i in range(m):
    q = input().split()
    x = int(q[0])
    y = int(q[1])
    z = int(q[2])
    # Krawędź x-y
    a[x][y] = True
    a[y][x] = True
    # Waga krawędzi x-y
    w[x][y] = z
    w[y][x] = z
print()
# Rozpoczynamy algorytm
d = MAXINT
dhx = 0
v0 = 0
tsp(v0)
if sptr > 0:
    for i in range(sptr):
        print(s[i],end=" ")
    print(v0)
    print(" d =",d)
else:
    print("NO HAMILTONIAN CYCLE")
print()
# Usuwamy tablice dynamiczne
del s,sh,vs
for i in range(n):
    a[i] = None
    w[i] = None
del a,w