program shuta;

type re=record
      a,max:longint;
      num:shortint;
     end;

var ta:array[1..80,1..80]of re;
    n,i,j,maxnum:longint;
    f1:text;

begin
 assign(f1,'shuta.in');
 reset(f1);

 readln(f1,n);

 for i:=1 to n do
  for j:=1 to i do
   read(f1,ta[i,j].a);

 close(f1);

 for i:=1 to n do
  ta[n,i].max:=ta[n,i].a;

 for i:=n-1 downto 1 do
  for j:=1 to i do
   if ta[i+1,j].max>ta[i+1,j+1].max then
   begin
    ta[i,j].max:=ta[i+1,j].max+ta[i,j].a;
    ta[i,j].num:=j; end else
   begin
    ta[i,j].max:=ta[i+1,j+1].max+ta[i,j].a;
    ta[i,j].num:=j+1;
   end;


 assign(f1,'shuta.out');
 rewrite(f1);

 writeln(f1,ta[1,1].max);

 j:=1;
 for i:=1 to n do
 begin
  write(f1,ta[i,j].a,' ');
  j:=ta[i,j].num;
 end;
 close(f1);
end.