program cch(input,output,f1,f2);
var
 f1,f2:text;
 data,way:array[1..100,1..100] of integer;
 a:array[1..100,1..100] of longint;
 i,j,n,p:integer;

begin
 assign(f1,'shuta.in');
 assign(f2,'shuta.out');
 reset(f1);
 rewrite(f2);
 readln(f1,n);
 for i:=1 to n do
  for j:=1 to i do begin
   read(f1,data[i,j]);
   a[i,j]:=data[i,j];
  end;
 for i:=n-1 downto 1 do
  for j:=1 to i do
   if a[i+1,j]>a[i+1,j+1] then begin a[i,j]:=a[i,j]+a[i+1,j]; way[i,j]:=j; end
                                else begin a[i,j]:=a[i,j]+a[i+1,j+1]; way[i,j]:=j+1; end;
 writeln(f2,a[1,1]);
 write(f2,data[1,1],' '); p:=1;
 for i:=1 to n-1 do begin
  write(f2,data[i+1,way[i,p]],' ');
  p:=way[i,p];
 end;
 close(f1);
 close(f2);
end.