program shuta;
Type
fxz=array[1..80,1..80] of longint;
Var
a,b,way:fxz;
i,j,n:longint;
f1,f2:text;
begin
assign(f1,'shuta.in');
assign(f2,'shuta.out');
reset(f1);rewrite(f2);
readln(f1,n);
for i:=1 to n do
 begin
 for j:=1 to i do read(f1,a[i,j]);
 readln(f1);
 end;
 b:=a;
for i:=n-1 downto 1 do
 for j:=1 to i do
 begin
 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;
 end;
writeln(f2,a[1,1]);
write(f2,b[1,1],' ');
for i:=1 to n-1 do
begin j:=way[i,j];
write(f2,b[i+1,j],' ');
end;
close(f1);close(f2);
end.