#include <stdio.h>
void my_Prim(int n);
//data for Prim
int graph[1005][1005];
int mincost[1005];
int adjvex[1005];
int main(void) {
int num_input = 0;
scanf("%d", &num_input);
//other data
int i = 0, j = 0;
int n = 0;
int price_qs[1005];
while(num_input--) {
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &price_qs[i]);
}
//init graph
for (i = 0; i < n; ++i){
mincost[i] = adjvex[i] = 0;
for (j = 0; j < n; ++j) {
scanf("%d", &graph[i][j]);
if (i != j) {
graph[i][j] += price_qs[i] + price_qs[j];
}
}
}
my_Prim(n);
}
return 0;
}
void my_Prim(int n){
int sum = 0;
int i = 0, j= 0, k = 0;
for (i = 0; i < n; ++i) {
mincost[i] = graph[0][i];
adjvex[i] = 0;
}
int min = 65535;
for (i = 1; i < n; ++i) {
min = 65535;
j = 1; k = 0;
while (j < n) {
if (mincost[j] != 0 && mincost[j] < min) {
min = mincost[j];
k = j;
}
++j;
}
sum += min;
mincost[k] = 0;
for (j = 1; j < n; ++j) {
if (mincost[j] != 0 && graph[k][j] < mincost[j]) {
mincost[j] = graph[k][j];
adjvex[j] = k;
}
}
}
printf("%d\n", sum);
}
