program shuta;
  var
    a,b:array[1..80,1..80]of longint;
    n,i,j,k:integer;
    f1,f2:text;
    procedure ini;
      var
        i,j:integer;
      begin
        assign(f1,'shuta.in');reset(f1);
        assign(f2,'shuta.out');rewrite(f2);
        read(f1,n);
        for i:=1 to n do begin
          for j:=1 to i do begin
            read(f1,a[i,j]);
            b[i,j]:=a[i,j];
          end;
          readln(f1);
        end;
        close(f1);
      end;
  begin
    ini;
    for i:=n-1 downto 1 do
      for j:=1 to i do
        if a[i+1,j]>a[i+1,j+1] then a[i,j]:=a[i+1,j]+a[i,j]
        else a[i,j]:=a[i+1,j+1]+a[i,j];
    writeln(f2,a[1,1]);
    write(f2,b[1,1]);
    k:=1;
    for i:=2 to n do
      for j:=k to i-1 do
        if a[i,j]>a[i,j+1]then begin
          write(f2,' ',b[i,j]);
          k:=j;
          break;
        end
        else begin
          write(f2,' ',b[i,j+1]);
          k:=j+1;
          break;
        end;
    close(f2);
  end.