#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+;

struct edge{

    int a,b;

    double w;

}e[N];

int p[N];

int a[N];

int n;

bool cmp(edge a,edge b)

{

    return a.w<b.w;

}

int find(int x)

{

    if(p[x]!=x)

        p[x]=find(p[x]);

    return p[x];

}

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        cin>>n;

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

            p[i]=i;

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

            cin>>a[i];

        int num=;

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

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

            {

                int len;

                cin>>len;

                if(i!=j)

                {

                    e[num].a=i;

                    e[num].b=j;

                    e[num++].w=len+a[i]+a[j];

                }

            }

        sort(e,e+num,cmp);

        int sum=;

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

        {

            int a=find(e[i].a);

            int b=find(e[i].b);

            int w=e[i].w;

            if(a!=b)

            {

                p[a]=b;

                sum+=w;

            }

        }

        cout<<sum<<endl;

    }

    return ;

}