program bly(input,output);
type
  t1=array[-2..100,-2..100] of longint;
  t2=array[1..100] of longint;
var
  a:t1;
  k,max,s:t2;
  i,j,x:longint;
  f1,f2:text;
  n,max0,k0,k1:longint;
begin
  assign(f1,'shuta.in');
  reset(f1);
  readln(f1,n);
  for i:=1 to n do begin
    for j:=1 to i do begin
      read(f1,a[i,j]);
    end;
  readln(f1);
  end;
  close(f1);
  for j:=1 to n do begin
    if a[n,j]>max0 then begin k0:=j; max0:=a[n,j]; end;
  end;
  inc(x); s[x]:=a[n,k0]; inc(x);
  for i:=n downto 1 do begin
    k[1]:=k0;
    max[1]:=max0+a[i-1,k0]+a[i-2,k[1]];
    k[2]:=k0;
    max[2]:=max0+a[i-1,k0]+a[i-2,k[2]-1];
    k[3]:=k0-1;
    max[3]:=max0+a[i-1,k0-1]+a[i-2,k[3]];
    k[4]:=k0-1;
    max[4]:=max0+a[i-1,k0-1]+a[i-2,k[4]-1];
    for j:=1 to 4 do begin
      if max[j]>max[5] then begin
         k1:=j; max[5]:=max[j];
      end;
    end;
    if k1>2 then k0:=k0-1;
    max0:=max0+a[i-1,k0]; s[x]:=a[i-1,k0]; inc(x);
    for j:=1 to 5 do max[j]:=0;
  end;
  assign(f2,'shuta.out');
  rewrite(f2);
  writeln(f2,max0);
  for i:=n downto 1 do begin
    write(f2,s[i]); write(f2,' ');
  end;
  close(f2);
end.