#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, m;
vector<P> adj[301];
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> m;
adj[0].push_back({m, i});
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
cin >> m;
if(!m)
continue;
adj[i].push_back({m, j});
}
int cnt = 0, ans = 0, bias, nxt;
vector<int> isin(n + 1, 0);
priority_queue<P, vector<P>, greater<P>> pq;
isin[0] = 1;
for(auto i : adj[0])
pq.push(i);
while(cnt < n) {
bias = pq.top().first;
nxt = pq.top().second;
pq.pop();
cout << bias << '\n';
if(isin[nxt])
continue;
cnt++;
ans += bias;
isin[nxt] = 1;
for(auto i : adj[nxt])
if(!isin[i.second])
pq.push(i);
}
cout << ans;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IFA7CgppbnQgbWFpbigpIHsKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4udGllKDApOwoJCglpbnQgbiwgbTsKCXZlY3RvcjxQPiBhZGpbMzAxXTsKCQoJY2luID4+IG47Cglmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCWNpbiA+PiBtOwoJCWFkalswXS5wdXNoX2JhY2soe20sIGl9KTsKCX0KCWZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQoJCWZvcihpbnQgaiA9IDE7IGogPD0gbjsgaisrKSB7CgkJCWNpbiA+PiBtOwoJCQkKCQkJaWYoIW0pCgkJCQljb250aW51ZTsKCQkJCgkJCWFkaltpXS5wdXNoX2JhY2soe20sIGp9KTsKCQl9CgkJCglpbnQgY250ID0gMCwgYW5zID0gMCwgYmlhcywgbnh0OwoJdmVjdG9yPGludD4gaXNpbihuICsgMSwgMCk7Cglwcmlvcml0eV9xdWV1ZTxQLCB2ZWN0b3I8UD4sIGdyZWF0ZXI8UD4+IHBxOwoJCglpc2luWzBdID0gMTsKCWZvcihhdXRvIGkgOiBhZGpbMF0pCgkJcHEucHVzaChpKTsKCQkKCXdoaWxlKGNudCA8IG4pIHsKCQliaWFzID0gcHEudG9wKCkuZmlyc3Q7CgkJbnh0ID0gcHEudG9wKCkuc2Vjb25kOwoJCXBxLnBvcCgpOwoJCQoJCWNvdXQgPDwgYmlhcyA8PCAnXG4nOwoJCQoJCWlmKGlzaW5bbnh0XSkKCQkJY29udGludWU7CgkJCQoJCWNudCsrOwoJCWFucyArPSBiaWFzOwoJCWlzaW5bbnh0XSA9IDE7CgkJCgkJZm9yKGF1dG8gaSA6IGFkaltueHRdKQoJCQlpZighaXNpbltpLnNlY29uZF0pCgkJCQlwcS5wdXNoKGkpOwoJfQoJCgljb3V0IDw8IGFuczsKfQ==