program dt;
type
shuzu=array[1..100,1..100]of integer;
var
t,b:shuzu;
c,i,j,n,max,temp:integer;
f1,f2:text;
l:array[1..100] of integer;
begin
assign(f1,'shuta.in');reset(f1);
assign(f2,'shuta.out');rewrite(f2);
readln(f1,n);
for i:=1 to n do
begin
for j:=1 to i do
begin
read(f1,t[i,j]);
end;
readln(f1);
end;
max:=0; l[1]:=t[1,1];
for i:=1 to n do b[n,i]:=t[n,i];
for i:=n-1 downto 1 do begin
  for j:=1 to i do begin
     if b[i+1,j]>b[i+1,j+1] then
     begin
     max:=b[i+1,j];
     l[i+1]:=t[i+1,j];
     end
     else begin
     max:=b[i+1,j+1]; l[i+1]:=t[i+1,j+1]; end;
   b[i,j]:=t[i,j]+max;
end;
end;
writeln(f2,b[1,1]);
for i:=1 to n do
  write(f2,l[i],' ');
close(f2);
end.