#include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 #include<string>

 #define cl(a,b) memset(a,b,sizeof(a))

 #define debug(x) cerr<<#x<<"=="<<(x)<<endl

 using namespace std;

 typedef long long ll;

 const int maxn=;

 int f[maxn],tol,n,m;

 struct _edge

 {

     int u,v,w;

 }edge[maxn*maxn*maxn];

 bool cmp(_edge a,_edge b)

 {

     return a.w<b.w;

 }

 void addedge(int u,int v,int w)

 {

     edge[tol].u=u;

     edge[tol].v=v;

     edge[tol].w=w;

     tol++;

 }

 int _find(int x)

 {

     if(f[x]==-) return x;

     else return f[x]=_find(f[x]);

 }

 int kruskal()

 {

     cl(f,-);

     sort(edge,edge+tol,cmp);

     int cnt=,ans=;

     int u,v,w,f1,f2;

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

     {

         u=edge[i].u;

         v=edge[i].v;

         w=edge[i].w;

         f1=_find(u);

         f2=_find(v);

         if(f1!=f2)

         {

             ans+=w;

             f[f1]=f2;

             cnt++;

         }

         if(cnt==n-) break;

     }

     return ans;

 }

 int main()

 {

     while(scanf("%d",&n)!=EOF&&n)

     {

         tol=;

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

         {

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

             {

                 int x;

                 scanf("%d",&x);

                 addedge(i,j,x);

             }

         }

         scanf("%d",&m);

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

         {

             int x,y;

             scanf("%d%d",&x,&y);

             addedge(x-,y-,);

             addedge(y-,x-,);

         }

         printf("%d\n",kruskal());

     }

     return ;

 }

 /*

 3

 0 990 692

 990 0 179

 692 179 0

 1

 1 2

 */