#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#define INF 123456789

using namespace std;

int n, a[], head[], cnt, pre[], Ans, ans[], dis[], TANS[], t;

bool vis[];

queue<int> Q;

struct edge {

    int nxt, u, v, w;

}ed[*];

inline void addedge(int x, int y, int z) {

    ed[++cnt].nxt = head[x];

    head[x] = cnt;

    ed[cnt].u = x, ed[cnt].v = y, ed[cnt].w = z;

}

inline int spfa(int s) {

    while (!Q.empty()) Q.pop();

    memset(vis, , sizeof(vis));

    for(int i=; i<=n; i++) dis[i] = -INF;

    Q.push(s), dis[s] = a[s], vis[s] = , pre[s] = ;

    while (!Q.empty()) {

        int u = Q.front(); Q.pop();

        for(int i=head[u]; i; i=ed[i].nxt) {

            if(dis[ed[i].v] < dis[u] + ed[i].w) {

                dis[ed[i].v] = dis[u] + ed[i].w;

                pre[ed[i].v] = u;

                if(!vis[ed[i].v])

                    vis[ed[i].v] = , Q.push(ed[i].v);

            }

        }

        vis[u] = ;

    }

    for(int i=; i<=n; i++) {

        if(dis[i] > Ans) {

            Ans = dis[i];

            for(int j=; j<=n; j++) ans[j] = pre[j];

            t = i;

        }

    }

}

int main() {

    scanf("%d", &n);

    int x;

    for(int i=; i<=n; i++) scanf("%d", &a[i]);

    for(int i=; i<=n; i++) {

        for(int j=i+; j<=n; j++) {

            scanf("%d", &x);

            if(x == ) addedge(i, j, a[j]);

        }

    }

    for(int i=; i<=n; i++)

        spfa(i);

    cnt = ;

    for(int i=t; i; i=ans[i]) TANS[++cnt] = i;

    for(int i=cnt; i>=; i--) printf("%d ", TANS[i]);

    printf("\n%d", Ans);

}