{решение задачи коммивояжера методом ветвей и границ}
program commivoyager;
const
 Max=20;
 Infty=30000;    {бесконечность, которая ставится в клетки}
 ToInfty=20000;  {если такое число появилось в клетке, то это бесконечность}
 MaxW=65535;
type
 tmatrix=record  {матрица - реально подматрица исходной}
         size:byte;
         indi,indj,indirev,indjrev:array [1..Max] of byte;
  {номера строк и столбцов до вычеркиваний и обратные к ним функции}
         data:array [1..Max,1..Max] of word;
        end;
 pmatrix=^tmatrix;
 tperm=record
        size:byte;
        dir,rev:array [1..Max] of 0..Max;
  {частичное решение как прямая и обратная перестановки}
       end;
 pperm=^tperm;
 node=record      {узел дерева обхода}
       c:pmatrix; {текущая подматрица}
       solv:pperm; {частичное решение}
       est,got:word; {прогнозируемая и полученная оценки - в текущей}
                     {версии всегда совпадают}
      end;
var
 best:word;     {лучший результат}
 bsolv:pperm;   {лучшая перестановка}
 main:node;     {основная задача}

function to0(var c:tmatrix):word; {функция получает нули в строках и}
            { столбцах матрицы и выдает сумму вычтенных ей элементов}
 var
  i,j:byte;
  m,res:word;
 begin
  res:=0;
  with c do
  begin
   for i:=1 to size do
   begin
    m:=MaxW;
    for j:=1 to size do
     if data[i,j]<=m then
      m:=data[i,j];
    for j:=1 to size do
     dec(data[i,j],m);
    inc(res,m);
   end;
   for j:=1 to size do
   begin
    m:=MaxW;
    for i:=1 to size do
     if data[i,j]<=m then
      m:=data[i,j];
    for i:=1 to size do
     dec(data[i,j],m);
    inc(res,m);
   end;
  end;
  to0:=res;
 end;

procedure chooseedge(const c:tmatrix;var im,jm:byte);
 var      {выбор нуля, по которому будем ветвиться}
  i,j,k:byte;
  m,m1:word;
 begin
  m:=0;
  im:=0;
  jm:=0;
  with c do
  begin
   for i:=1 to size do
   begin
    for j:=1 to size do
     if data[i,j]=0 then break;
    m1:=MaxW;
    for k:=1 to size do
     if (data[i,k]<=m1) and (j<>k) then
      m1:=data[i,k];
    if m1>=m then
    begin
     m:=m1;
     im:=i;
     jm:=j;
    end;
   end;
  end;
 end;

procedure add(p:pperm;i,ip:byte;var res:pperm);
 begin   {добавление ребра i->ip к частичному решению}
  new(res);
  res^:=p^;
  res^.dir[i]:=ip;
  res^.rev[ip]:=i;
 end;

procedure process(var n:node); {обход узла}
 var
  i,j,k,l,i1,j1:byte;
  n1,n2:node;
  first:boolean;
  los:word;              {потери на данном шаге}
 begin
  with n do
  begin
   if c^.size=1 then     {если осталась матрица 1х1 (в ней всегда 0)}
   begin
    if best>=got then
    begin
     best:=got;
     if bsolv<>nil then dispose(bsolv);
     with n.c^ do
      add(n.solv,indi[1],indj[1],bsolv); {делаем из частичного решения}
                                         {полное и помещаем в bsolv}
    end
   end
   else
   begin
    if est<best then  {если текущая оценка меньше лучшего результата}
    begin
     chooseedge(c^,i,j);
     new(n1.c);       {составляем матрицу с вычеркнутыми строкой и столбцом}
     n1.c^.size:=n.c^.size-1;
     fillchar(n1.c^.indi,sizeof(n1.c^.indi),0);
     fillchar(n1.c^.indj,sizeof(n1.c^.indj),0);
     fillchar(n1.c^.indirev,sizeof(n1.c^.indirev),0);
     fillchar(n1.c^.indjrev,sizeof(n1.c^.indjrev),0);
     i1:=0;
     first:=true;
     for k:=1 to n.c^.size do
      if (k<>i) then
      begin
       inc(i1);
       n1.c^.indi[i1]:=n.c^.indi[k];
       n1.c^.indirev[n.c^.indi[k]]:=i1;
       j1:=0;
       for l:=1 to n.c^.size do
        if (l<>j) then
        begin
         inc(j1);
         if first then
         begin
          n1.c^.indj[j1]:=n.c^.indj[l];
          n1.c^.indjrev[n.c^.indj[l]]:=j1;
         end;
         n1.c^.data[i1,j1]:=n.c^.data[k,l];
        end;
       first:=false;
      end;
     with n.c^ do
     begin
      k:=indi[i];
      l:=indj[j];
     end;
     add(n.solv,k,l,n1.solv); {новое частичное решение}
     if n1.c^.size>1 then   {здесь ищем начало и конец участка пути}
     begin                  {и запрещаем замыкать его, если, конечно,}
      with n1.solv^ do      {не получится полный цикл}
      begin
       i1:=k;
       while rev[i1]>0 do
        i1:=rev[i1];
       j1:=l;
       while dir[j1]>0 do
        j1:=dir[j1];
      end;
      with n1.c^ do
       if (indirev[j1]>0) and (indjrev[i1]>0) then
        data[indirev[j1],indjrev[i1]]:=Infty;
     end;
     los:=to0(n1.c^);
     if los<ToInfty then
     begin
      n1.est:=n.est+los;  {посчитали оценку для новой матрицы}
      n1.got:=n.got+los;
      process(n1);        {и сделали шаг вперед}
     end;
     n.c^.data[i,j]:=Infty; {теперь запрещаем выбор варианта i->j}
     los:=to0(n.c^);
     if los<ToInfty then
     begin
      inc(n.est,los);     {посчитали оценку}
      inc(n.got,los);
      process(n);         {и сделали шаг вправо (вперед и вбок)}
     end;
    end;
   end;
  end;
 end;

procedure readdata(var main:node);
 var
  i,j:byte;
 begin
  assign(input,'input.cmm');
  reset(input);
  new(main.c);
  new(main.solv);
  with main.c^ do
  begin
   read(size);
   for i:=1 to size do
   begin
    indi[i]:=i;      {изначально все индексы указывают на себя}
    indj[i]:=i;
    indirev[i]:=i;
    indjrev[i]:=i;
   end;
   for i:=1 to size do
    for j:=1 to size do
    begin
     read(data[i,j]);
     if i=j then
      data[i,j]:=Infty; {сразу запрещаем петли}
    end;
  end;
  with main.solv^ do
  begin
   size:=main.c^.size;
   fillchar(dir,sizeof(dir),0); {пустое частичное решение}
   fillchar(rev,sizeof(rev),0);
  end;
  main.est:=to0(main.c^);
  main.got:=main.est;
  best:=MaxW;
  new(bsolv);
  close(input);
 end;

procedure out;
 var
  i:byte;
 begin
  write('Shortest cycle: ');
  i:=1;
  repeat
   write(i,' ');
   i:=bsolv^.dir[i];  {проходимся по прямой перестановке}
  until i=1;
  writeln;
  writeln('Its length: ',best);
 end;

Begin
 readdata(main);
 process(main);
 out;
End.