hdu 1102

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <list>
#include <vector>

using namespace std;
#define PD(x) (scanf("%d",&x))
#define PP(a,b) (scanf("%d%d",&a,&b))
#define PR(a) (printf("%d
",a))
#define N 105


int map[N][N];
int p;
int n;
int q;
int ar[N];
struct P
{
	int dis;
	int s,t;
	P(int a,int b,int c):s(a),t(b),dis(c){}
};
vector<P> T;
int find(int a,int *s)
{
	int temp = a;
	while(s[temp]!=temp)
	{
		temp = s[temp];
	}

	int c = a;
	int r = a;
	while(s[c]!=c)
	{
		r = c;
		c = s[c];
		s[r] = temp;
	}
	return temp;
}
void unions(int a,int b,int *s)
{
	s[b] = a;
}
bool cmp(P aa,P bb)
{
	return aa.dis<bb.dis;
}

void init()
{
  while(scanf("%d",&n)!=EOF)
  {
	  for(int i=0;i<n;i++)
		  for(int j=0;j<n;j++)
			  PD(map[i][j]);
	  for(int i=0;i<n;i++)
		  ar[i] = i;
	  PD(q);

	  for(int i=0;i<q;i++)
	  {
		  int a,b;
		  PP(a,b);
		  map[a-1][b-1] = 0;
		  map[b-1][a-1] = 0;
		  a = find(a-1,ar);
		  b = find(b-1,ar);
		  unions(a,b,ar);
	  }

	  if(!T.empty()) T.clear();

	  for(int i = 0;i<n;i++)
		  for(int j = 0;j<n;j++)
			  if(map[i][j])
			  {
				  P var(i,j,map[i][j]);
				  T.push_back(var);
			  }

		  int sum = 0 ;
		 sort(T.begin(),T.end(),cmp);

		  for(int i=0;i<(int)T.size();i++)
		  {
			  int a = find(T[i].s,ar);
			  int b = find(T[i].t,ar);
			  if(a!=b)
			  {
				  sum += T[i].dis;
				  unions(a,b,ar);
			  }
		  }
		  PR(sum);
  }
}
int main()
{
	init();
	return 0;
}