{利用计算最佳连通分支算法即可求得}
program miner;
const
  maxv=20;
var
  link,longlink:array[1..maxv,1..maxv] of boolean;
  a:array[1..maxv,1..maxv] of 0..1;
  f:array[1..maxv] of boolean;
  w:array[1..maxv] of integer;
  v,e,k,i,j,s,max,maxk:integer;
procedure init;
 begin
  assign(input,'miner.in');
  reset(input);
  assign(output,'miner.out');
  rewrite(output);
  fillchar(longlink,sizeof(longlink),false);
  fillchar(link,sizeof(link),false);
  readln(v);
  for i:=1 to v do
    read(w[i]);
  readln;
  for i:=1 to v do
    begin
      for j:=i+1 to v do
        begin
          read(a[i,j]);
          if a[i,j]=1
             then begin
                    link[i,j]:=true;
                    link[j,i]:=true;
                  end;
        end;{for j}
      readln;
    end;{for i}
    for i:=1 to v do      begin
     for j:=1 to v do
       write(link[i,j]:6);
       writeln;end;
 end;{init}
procedure bibao;
 begin
  longlink:=link;
  for k:=1 to v do
    for i:=1 to v do
      for j:=1 to v do
        longlink[i,j]:=longlink[i,j] or (longlink[i,k] and longlink[k,j]);
 end;{bibao}
procedure dfs(i:integer);
  begin
    write(i,' ');
    f[i]:=true;
    for j:=1 to v do
      if (not f[j]) and longlink[i,j]
         then dfs(j);
 end;{dfs}
begin{main}
 init;
 bibao;
 max:=0;
 for i:=1 to v do
   begin
    s:=0;
    for j:=1 to v do
      if longlink[i,j]
        then s:=s+w[j];
   if s>max
      then begin
             max:=s;
             maxk:=i;
           end;
  end;
 fillchar(f,sizeof(f),false);
 dfs(maxk);
 writeln;
 write(max);
 close(input);
 close(output);
end.
//delphi/7192