program TimDuongDiCucTieu;

const

max = 20;

maxC = 20 * 100 + 1; {+8}

var

C: array[1..max, 1..max] of Integer;{Ma tran chi phi}

X, BestWay: array[1..max + 1] of Integer; {X do thi cac kha nang, BestWay de ghi nhan nghiem}

T: array[1..max + 1] of Integer; {Ti de luu chi phi di tu X1 den Xi}

Free: array[1..max] of Boolean; {Free de danh dau, Free = True neu chua di qua tp i}

m, n: Integer;

MinSpending: Integer;{Chi phi hanh trinh toi uu}

procedure Nhap;

var

i, j, k: Integer;

begin

ReadLn(n, m);

for i := 1 to n do

for j := 1 to n do

if i = j then C[i, j] := 0 else C[i, j] := maxC; {Khoi tao bang chi phi ban dau}

for k := 1 to m do

begin

ReadLn(i, j, C[i, j]);

C[j, i] := C[i, j]; {Chi phi nhu nhau trên 2 chieu}

end;

end;

procedure Khoitao; {Khoi tao}

begin

FillChar(Free, n, True);

Free[1] := False; {Cac thanh pho la chua di qua ngoai tru thanh pho 1}

X[1] := 1; {Xuat phat tu thanh pho 1}

T[1] := 0; {Chi phi tai thanh pho xuat phat la 0}

MinSpending := maxC;

end;

procedure Thudi(i: Integer); {Thu cac cach chon xi}

var

j: Integer;

begin

for j := 2 to n do {Thu cac thanh pho tu 2 den n}

if Free[j] then {Neu gap thanh pho chua di qua}

begin

X[i] := j; {Thu di}

T[i] := T[i - 1] + C[x[i - 1], j]; {Chi phi := Chi phi buoc truoc + chi phi duong di truc tiep}

if T[i] < MinSpending then {Hien nhien neu co dieu nay thi C[x[i-1],j]< +8 roi }

if i < n then {Neu chua den duoc xn}

begin

Free[j] := False; {Ðanh dau thành pho vua thu}

Try(i + 1); {Tim cac kha nang chon xi+1}

Free[j] := True; {Bo dánh dau}

end

else

if T[n] + C[x[n], 1] < MinSpending then {Tu xn quay lai 1 van ton chi phi it hon truoc}

begin {Cap nhat BestConfig}

BestWay := X;

MinSpending := T[n] + C[x[n], 1];

end;

end;

end;

procedure InKetqua;

var

i: Integer;

begin

if MinSpending = maxC then WriteLn('Khong ton tai duong di')

else

for i := 1 to n do Write(BestWay[i], '->');

WriteLn(1);

WriteLn('Chi phi: ', MinSpending);

end;

begin

Assign(Input, 'vao.inp'); Reset(Input);

Assign(Output,'ra.out'); Rewrite(Output);

Nhap;

KhoiTao;

Thudi(2);

InKetqua;

Close(Input); Close(Output);

end.