Program shuta;

Type
sc=array [0..80,0..80] of integer;
sc1=array [1..80] of integer;

Var
s,s1:sc;
k:sc1;
i,j,n,p,q,max1,max:integer;
f1,f2:text;

Begin
assign(f1,'shuta.in');
assign(f2,'shuta.out');
reset(f1);
rewrite(f2);
for i:=0 to 80 do
 for j:=0 to 80 do
  s1[i,j]:=0;
readln(f1,n);
for i:=1 to n do begin
 j:=0;
 repeat
  j:=j+1;
  read(f1,s[i,j]);
 until(j=i);
 readln(f1);
end;
s1:=s;
for i:=n downto 1 do begin
 j:=0;
 repeat
  j:=j+1;
  if s1[i-1,j]+s1[i,j]<s1[i-1,j]+s1[i,j+1] then begin
   s1[i-1,j]:=s1[i-1,j]+s1[i,j+1];
  end
  else begin
   s1[i-1,j]:=s1[i-1,j]+s1[i,j];
  end;
 until (j=i);
 max1:=0;
 for p:=1 to i do
  if s1[i,p]>max1 then begin
   max:=s[i,p];
   max1:=s1[i,p];
  end;
 k[i]:=max;
end;

writeln(f2,s1[1,1]);
for i:=1 to n do write(f2,k[i],' ');
close(f1);
close(f2);
End.