#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <cmath>#include <algorithm>#define lson l, m, rt<<1#define rson m+1, r, rt<<1|1using namespace std;typedef long long int LL;const int MAXN = 0x3f3f3f3f;const int MIN = -0x3f3f3f3f;const double eps = 1e-9;const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1}, {1,1},{1,-1},{-1,-1}};const int MAX = 1000+10;int edge[MAX][MAX], lowcost[MAX];int t, n, pri[MAX];void prim(int u0) { int sum = 0, i, j, v; for (i = 1; i <= n; ++i) lowcost[i] = edge[u0][i]; lowcost[u0] = -1; for (i = 1; i < n; ++i) { int min = MAXN; v = -1; for (j = 1; j <= n; ++j) { if (min > lowcost[j] && lowcost[j] != -1) { v = j; min = lowcost[j]; } } if (v != -1) { sum += lowcost[v]; lowcost[v] = -1; for (j = 1; j <= n; ++j) { if (edge[v][j] < lowcost[j] && lowcost[j] != -1) { lowcost[j] = edge[v][j]; } } } } printf("%dn", sum);}int main(void){ scanf("%d", &t); int i, j, k; while (t--) { memset(edge, 0, sizeof(edge)); scanf("%d", &n); for (i = 1; i <= n; ++i) scanf("%d", &pri[i]); for (i = 1; i <= n; ++i) { for (j = 1; j <= n; ++j) { scanf("%d", &edge[i][j]); edge[i][j] += (pri[i] + pri[j]); } } prim(1); } return 0;}
