#include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn = +;

 const int MAX = ;//无穷远

 int n;

 int cost[maxn];

 int Edge[maxn][maxn];

 int lowcost[maxn];

 void Init()

 {

     cin>>n;

     for(int i=;i<n;i++)

     {//读入每个结点的适配器价值

         cin>>cost[i];

     }

     for(int i=;i<n;i++)

     {//建立邻接矩阵

         for(int j=;j<n;j++)

         {

             cin>> Edge[i][j];

             if(i == j) Edge[i][j] = MAX;

             else Edge[i][j] += cost[i]+cost[j];

         }

     }

     memset(lowcost,,sizeof(lowcost));

 }

 void prim()

 {

     int sum = ;

     //从源点0开始

     lowcost[] = -;//-1表示当前结点已经加入

     for(int i=;i<n;i++)

         lowcost[i] = Edge[][i];

     for(int i=;i<n;i++)

     {//把其他 n-1 个结点 扩展到生成树中

         int min = MAX,pos;

         for(int j=;j<n;j++)//找到权值最小的边

         {

             if(lowcost[j] != - && lowcost[j]<min)

             {

                 min = lowcost[j];pos = j;

             }

         }

         //将新顶点加入

         lowcost[pos] = -;

         sum += min;

         //更新lowcost数组

          for(int k=;k<n;k++)

          {

              if(lowcost[k] > Edge[pos][k])

              lowcost[k] = Edge[pos][k];

          }

      }

      cout<<sum<<endl;

 }

 int main()

 {

     int t;

     cin>>t;

     while(t--)

     {

         Init();

         prim();

     }

     return ;

 }