/**
* author: orzvanh14 ( )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n"
#define pi pair<int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "
#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n
#define LOG 19
const int INF = 1e18;
const int mod = 1e9+7;
const int N = 5e2 + 5;
int MOD = 998244353;
int bit[200000];
struct node{
int kc, u, hk;
bool operator<(const node& other) const {
return kc > other.kc;
}
};
struct edge{
int u, v, w;
friend bool operator < ( edge a, edge b){
return a.w < b.w;
}
};
vector<edge> adj;
int n;
int lab[N];
int a[N], b[N][N];
int get(int v){
if(lab[v] < 0) return v;
return lab[v] = get(lab[v]);
}
bool union_sets(int a, int b){
a = get(a);
b = get(b);
if(a != b){
if(lab[a] > lab[b]) swap(a, b);
lab[a] += lab[b];
lab[b] = a;
return true;
}
else return false;
}
void nhap(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
adj.push_back({0, i, a[i]});
}
for(int i = 1; i <= n;i++){
for(int j = 1; j <= n ; j++){
cin >> b[i][j];
}
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
adj.push_back({i, j, b[i][j]});
}
}
}
void solve(){
memset(lab, -1, sizeof(lab));
sort(adj.begin(), adj.end());
int ans = 0;
for(auto edges : adj){
if(union_sets( edges.u, edges.v ) ) ans += edges.w;
}
cout << ans << nn;
}
signed main() {
// freopen("piggyback.in", "r", stdin);
// freopen("piggyback.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
nhap();
solve();
return 0;
}
LyoqCiAqICAgIGF1dGhvcjogIG9yenZhbmgxNCAoICApCiAqICAgIGNyZWF0ZWQ6IDIzLjEyLjIwMjIgMTA6MDg6MDIKICogICAgdG9vIGxhenkgdG8gdXBkYXRlIHRpbWUKKiovCi8vIGkgd2FudHMgdG8gdGFrZSBpb2kKLy9iaW5odGluaHR1dGlua2hvbmdjYXljdW5odW5nbW90a2hpa2hvbmdjb250dXRpbm51YWxhdHV5ZXR2b25nCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgaW50IGxvbmcgbG9uZwojZGVmaW5lIG5uICJcbiIKI2RlZmluZSBwaSBwYWlyPGludCwgaW50PgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGViIGVtcGxhY2VfYmFjawojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIFRBU0sgIiAiCgojZGVmaW5lIG1zKGEsIHgpIG1lbXNldChhLCB4LCBzaXplb2YoYSkpCiNkZWZpbmUgYWxsKGEpIGEuYmVnaW4oKSwgYS5lbmQoKQojZGVmaW5lIEFsbChhLCBuKSBhICsgMSwgYSArIDEgKyBuCgojZGVmaW5lIExPRyAxOQoKCmNvbnN0IGludCBJTkYgPSAxZTE4Owpjb25zdCBpbnQgbW9kID0gMWU5Kzc7CmNvbnN0IGludCBOID0gNWUyICArIDU7CmludCBNT0QgPSA5OTgyNDQzNTM7CmludCBiaXRbMjAwMDAwXTsKc3RydWN0IG5vZGV7CglpbnQga2MsIHUsIGhrOwoJYm9vbCBvcGVyYXRvcjwoY29uc3Qgbm9kZSYgb3RoZXIpIGNvbnN0IHsKICAgICAgICByZXR1cm4ga2MgPiBvdGhlci5rYzsKICAgIH0KfTsKc3RydWN0IGVkZ2V7CglpbnQgdSwgdiwgdzsKCWZyaWVuZCBib29sIG9wZXJhdG9yIDwgKCBlZGdlIGEsIGVkZ2UgYil7CgkJcmV0dXJuIGEudyA8IGIudzsKCX0KfTsKdmVjdG9yPGVkZ2U+IGFkajsKaW50IG47CmludCBsYWJbTl07CmludCBhW05dLCBiW05dW05dOwppbnQgZ2V0KGludCB2KXsKCWlmKGxhYlt2XSA8IDApIHJldHVybiB2OwoJcmV0dXJuIGxhYlt2XSA9IGdldChsYWJbdl0pOwp9CmJvb2wgdW5pb25fc2V0cyhpbnQgYSwgaW50IGIpewoJYSA9IGdldChhKTsKCWIgPSBnZXQoYik7CglpZihhICE9IGIpewoJCWlmKGxhYlthXSA+IGxhYltiXSkgc3dhcChhLCBiKTsKCQlsYWJbYV0gKz0gbGFiW2JdOwoJCWxhYltiXSA9IGE7CgkJcmV0dXJuIHRydWU7Cgl9CgllbHNlIHJldHVybiBmYWxzZTsKCn0Kdm9pZCBuaGFwKCl7CiAgICBjaW4gPj4gbjsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKXsKICAgICAgICBjaW4gPj4gYVtpXTsKICAgICAgICBhZGoucHVzaF9iYWNrKHswLCBpLCBhW2ldfSk7CiAgICB9CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47aSsrKXsKICAgICAgICBmb3IoaW50IGogPSAxOyBqIDw9IG4gOyBqKyspewogICAgICAgICAgICBjaW4gPj4gYltpXVtqXTsKICAgICAgICB9CiAgICB9CiAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG47IGkrKyl7CiAgICAgICAgZm9yKGludCBqID0gaSArIDE7IGogPD0gbjsgaisrKXsKICAgICAgICAgICAgYWRqLnB1c2hfYmFjayh7aSwgaiwgYltpXVtqXX0pOwogICAgICAgIH0KICAgIH0KfQp2b2lkIHNvbHZlKCl7CgltZW1zZXQobGFiLCAtMSwgc2l6ZW9mKGxhYikpOwoJc29ydChhZGouYmVnaW4oKSwgYWRqLmVuZCgpKTsKCWludCBhbnMgPSAwOwoJZm9yKGF1dG8gZWRnZXMgOiBhZGopewoJCWlmKHVuaW9uX3NldHMoIGVkZ2VzLnUsIGVkZ2VzLnYgKSApIGFucyArPSBlZGdlcy53OwoJfQoJY291dCA8PCBhbnMgPDwgbm47Cn0Kc2lnbmVkIG1haW4oKSB7CgkvLyBmcmVvcGVuKCJwaWdneWJhY2suaW4iLCAiciIsIHN0ZGluKTsKCS8vIGZyZW9wZW4oInBpZ2d5YmFjay5vdXQiLCAidyIsIHN0ZG91dCk7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwoJY2luLnRpZSgwKTsKCWNvdXQudGllKDApOwogICAgbmhhcCgpOwogICAgc29sdmUoKTsKCXJldHVybiAwOwoKfQ==