1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
typedef long long ll;
7

8
struct Edge {
9
  int u, v, w;
10

11
  bool operator < (const Edge &A) const {
12
    return w < A.w;
13
  }
14
};
15

16
const int N = 2e3 + 5;
17
const int M = N * (N - 1);
18

19
int n, m, fa[N];
20
ll ans;
21
struct Edge e[M];
22

23
inline void init() {
24
  for (int i = 1; i <= n; ++i) {
25
    fa[i] = i;
26
  }
27
}
28

29
inline int find(const int &x) {
30
  return fa[x] == x ? x : fa[x] = find(fa[x]);
31
}
32

33
int main() {
34
  ios::sync_with_stdio(false);
35
  cin.tie(nullptr), cout.tie(nullptr);
36

37
  cin >> n;
38
  init();
39
  for (int i = 1; i <= n; ++i) {
40
    int v;
41
    cin >> v;
42
    e[++m].u = 0;
43
    e[m].v = i;
44
    e[m].w = v;
45
  }
46
  for (int i = 1; i <= n; ++i) {
47
    for (int j = 1; j <= n; ++j) {
48
      int w;
49
      cin >> w;
50
      if (i != j) {
51
        e[++m].u = i;
52
        e[m].v = j;
53
        e[m].w = w;
54
      }
55
    }
56
  }
57

58
  sort(e + 1, e + m + 1);
59
  for (int i = 1; i <= m; ++i) {
60
    int fu = find(e[i].u);
61
    int fv = find(e[i].v);
62
    if (fu != fv) {
63
      fa[fu] = fv;
64
      ans += e[i].w;
65
    }
66
  }
67

68
  cout << ans;
69
}