{*******************************************}
{* Program Name: Shuta                     *}
{* Input File: shuta.in                    *}
{* Output File: shuta.out                  *}
{* Date: 2008.7.24                         *}
{* Programmer: Peng Bo                     *}
{*******************************************}
program shuta;
type
  jl=record
    y,z:longint;
    x:byte;
    end;
  sz=array[1..80,1..80]of jl;
var
  s:sz;
  n:byte;
  j,k:byte;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure input;
var
  j,k:byte;
  f:text;
begin
  assign(f,'shuta.in');
  reset(f);
  readln(f,n);
  for j:=1 to n do
    for k:=1 to j do
      read(f,s[j,k].y);
  close(f);

  for j:=1 to n do
    s[n,j].z:=s[n,j].y;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure output;
var
  f:text;
  t,i:byte;
begin
  t:=1;
  assign(f,'shuta.out');
  rewrite(f);
  writeln(f,s[1,1].z);
  write(f,s[1,1].y,' ');
  for i:=1 to (n-1) do
  begin
    write(f,s[i+1,s[i,t].x].y,' ');
    t:=s[i,t].x;
  end;
  close(f);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure main;
var
  j,k:byte;
begin
  for j:=(n-1) downto 1 do
    for k:= 1 to j do
      if s[j+1,k].z>s[j+1,k+1].z
      then
      begin
        s[j,k].z:=s[j,k].y+s[j+1,k].z;
        s[j,k].x:=k;
      end
      else
      begin
        s[j,k].z:=s[j,k].y+s[j+1,k+1].z;
        s[j,k].x:=k+1;
      end;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  input;
  main;
  output;
end.