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

program TSProblem;

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

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

// Rekurencyjna procedura poszukiwania cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
// v - wierzchołek bieżący
//----------------------------------------------------
procedure TSP (v : integer);
var
  u : integer;
begin
  Sh [shptr] := v;              // zapamiętujemy na stosie bieżący wierzchołek
  inc (shptr);

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

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

var
  i, j, x, y, z : integer;
begin
  read (n, m); // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy struktury dynamiczne i inicjujemy je

  SetLength (S, n);
  SetLength (Sh, n);
  SetLength (visited, 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;
    visited [i] := false;
  end;
  sptr := 0;
  shptr := 0;

  // Odczytujemy dane wejściowe

  for i := 0 to m - 1 do
  begin
    read (x, y, z);
    A [x][y] := true; // Krawędź x-y
    A [y][x] := true;
    W [x][y] := z;    // Waga krawędzi x-y
    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 (visited, 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;
bool **A;                         // Macierz sąsiedztwa
int **W;                          // Macierz wag krawędzi
int *S, *Sh;                      // Stosy w tablicy
bool *visited;                    // Tablica odwiedzin

// Rekurencyjna procedura poszukiwania cyklu Hamiltona
// o najmniejszej sumie wag krawędzi
// v - wierzchołek bieżący
//----------------------------------------------------
void TSP (int v)
{
  int u;

  Sh [shptr++] = v;              // zapamiętujemy na stosie bieżący wierzchołek

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

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

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

  cin >> n >> m; // Czytamy liczbę wierzchołków i krawędzi

  // Tworzymy struktury dynamiczne i inicjujemy je

  S       = new int [n];
  Sh      = new int [n];
  visited = 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;
    }
    visited [i] = false;
  }
  sptr = shptr = 0;

  // Odczytujemy dane wejściowe

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> z;
    A [x][y] = A [y][x] = true; // Krawędź x-y
    W [x][y] = W [y][x] = z;    // Waga krawędzi x-y
  }

  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 [] visited;

  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, dh, sptr, shptr
Dim Shared As Byte Ptr Ptr A    ' Macierz sąsiedztwa
Dim Shared As Integer Ptr Ptr W ' Macierz wag krawędzi
Dim Shared As Integer Ptr S, Sh ' Stosy w tablicy
Dim Shared As Byte Ptr visited  ' Tablica odwiedzin

' 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

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

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

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

Open Cons For Input As #1

Input #1, n, m ' Czytamy liczbę wierzchołków i krawędzi

' Tworzymy struktury dynamiczne i inicjujemy je

S       = New Integer [n]
Sh      = New Integer [n]
visited = 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
  visited [i] = false
Next
sptr  = 0
shptr = 0

' Odczytujemy dane wejściowe

For i = 0 To m - 1
  Input #1, x, y, z
  A [x][y] = 1 ' Krawędź x-y
  A [y][x] = 1
  W [x][y] = z ' Waga krawędzi x-y
  W [y][x] = z
Next

Close #1

Print

' Rozpoczynamy algorytm

d  = MAXINT
dh = 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 [] visited

For i = 0 To n - 1
  Delete [] A [i]
  Delete [] W [i]
Next

Delete [] A
Delete [] W

End