#include<iostream>
using namespace std;
int n,p[102],h[102],sum,max1;
struct node{
	int x,y,w;
}no[10001];
bool flag[5051][5051];
int cmp(const void *a,const void *b)
{
	struct node *a1,*b1;
	a1=(struct node *)a;
	b1=(struct node *)b;
	return a1->w-b1->w;
}
void kruskal(int k);
void makeset();
int findset(int a);
void unionset(int a,int b);
int main()
{
	int i,j,a,b,k,c;
	while(scanf("%d",&n)!=EOF)
	{
		sum=n,k=0;
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%d",&a);
				no[k].x=i;
				no[k].y=j;
				no[k].w=a;
				k++;
			}
		makeset();
		scanf("%d",&c);
		memset(flag,false,sizeof(flag));
		for(i=0;i<c;i++)
		{
			scanf("%d%d",&a,&b);
			flag[a][b]=true;
			a=findset(a);
			b=findset(b);
			unionset(a,b);
		}
		if(sum==1)
			cout<<0<<endl;
		else
		{
			qsort(no,k,sizeof(no[0]),cmp);
			/*for(i=0;i<k;i++)
				cout<<no[i].w<<endl;*/
			max1=0;
			kruskal(k);
		}
			
	}
	return 0;
}
void makeset()
{
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
		h[i]=1;
	}
}
int findset(int a)
{
	while(a!=p[a])
		a=p[a];
	return a;
}
void unionset(int a,int b)
{
	if(a==b)
		return;
	if(h[a]==h[b])
	{
		p[a]=p[b];
		h[b]++;
	}
	else if(h[a]>h[b])
		p[b]=p[a];
	else
		p[a]=p[b];
	sum--;
}
void kruskal(int k)
{
	int a,b,i=0;
	while(1)
	{
		if(no[i].w!=0)
			break;
		else
			i++;
	}
	for(;i<k;i++)
	{
		a=no[i].x,b=no[i].y;
		if(flag[a][b])
			continue;
		a=findset(a);
		b=findset(b);
		if(a!=b)
		{
			max1+=no[i].w;
			unionset(a,b);
		}
		if(sum==1)
		{
			cout<<max1<<endl;
			return;
		}
	}
}