#include<bits/stdc++.h>
using namespace std;

// [1] 全局变量：n为村庄总数量，q为已建成的道路数量
int n , q;

// [2] 边结构体：存储单条道路的核心信息
struct stu{
	int value , x , y; // value：修建该道路的费用；x、y：道路连接的两个村庄编号
};
// [3] 全局数组：存储所有可修建的道路边集
vector<stu> arr;

// [4] 并查集父节点数组：存储每个村庄的父节点编号，用于判断村庄连通性
int fa[200];
// [5] 并查集深度数组：用于按秩合并优化，记录每个连通集合的树深度，避免树结构退化
int dep[510];


// [13] 跳转至cmp函数：定义道路的排序规则
bool cmp(stu x , stu y){
	// [14] 函数参数x、y：待比较的两条道路
	return x.value < y.value; // [15] 按道路修建费用升序排列，优先选择成本更低的道路
}
// [16] cmp函数注释完成，返回主函数继续注释

// [24] 跳转至find函数：查找节点x所在连通集合的根节点
int find(int x)
{
	// [25] 函数参数x：待查找根节点的村庄编号
	// [26] 循环向上遍历，直到找到父节点等于自身的根节点
	while(x != fa[x])
	{
		x = fa[x];
	}
	return x; // [27] 返回找到的根节点，用于判断两个村庄是否属于同一连通集合
}
// [28] find函数注释完成，返回主函数继续注释

// [30] 跳转至unite函数：合并x和y所在的两个连通集合
void unite(int x , int y)
{
	// [31] 函数参数x、y：待合并的两个村庄编号
	x = find(x); // [32] 查找x所在集合的根节点
	y = find(y); // [33] 查找y所在集合的根节点
	
	if( x == y ) return ; // [34] 若根节点相同，说明两村庄已连通，无需重复合并
	// [35] 按秩合并逻辑：将深度更小的树合并到深度更大的树下，保持树结构平衡，优化查询效率
	if(dep[x] > dep[y])
	{
		fa[y] = x;	
	}else if(dep[x] < dep[y])
	{
		fa[x] = y;
	}else
	{
		fa[y] = x;
		dep[x]++; // 两棵树深度相同时，合并后根节点的深度+1
	} 
}
// [36] unite函数注释完成，返回主函数继续注释

// [6] 主函数：程序运行入口
int main(){
	cin >>n; // [7] 读入村庄的总数量
	
	// [8] 双重循环读入邻接矩阵，将所有可修建的道路转为边集存储
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{	
			int num;
			cin >> num; // [9] 读入村庄i到村庄j修建道路的费用
			if(i == j) continue; // [10] 跳过村庄到自身的无效自环
			arr.push_back({num , i , j}); // [11] 将有效道路信息加入边集数组
		}
	} 
	
	// [12] 调用sort函数对所有道路按修建费用升序排序，排序规则由cmp函数定义，跳转至cmp函数注释
	sort(arr.begin() , arr.end() , cmp);
	
	// [16] 回到主函数sort执行后的代码
	// [17] 循环初始化并查集，为每个村庄初始化连通状态
	for(int i = 1 ; i <= n ; i++)
	{
		fa[i] = i; // [18] 每个村庄初始独立成一个连通集合，父节点设为自身
		dep[i] = 1; // [19] 每个连通集合的初始树深度设为1
	}
		
	cin >> q; // [20] 读入已建成的道路数量
	
	// [21] 循环处理所有已建成的道路，合并对应村庄的连通集合
	for(int i = 1 ; i <= q ; i++)
	{
		int a , b;
		cin >> a >> b; // [22] 读入已建成道路连接的两个村庄编号
		// [23] 调用find函数判断两个村庄是否已连通，跳转至find函数注释
		if(find(a) == find(b)) continue; // [28] 若已连通，无需重复合并，跳过当前道路
		// [29] 调用unite函数合并两个村庄所在的连通集合，跳转至unite函数注释
		unite(a , b);
	}
	
	// [37] 回到主函数已建道路处理完成后的代码
	// [38] 统计变量：sum为需要额外修建道路的最小总费用
	int sum = 0;
	// [39] 循环遍历排序后的道路，执行Kruskal算法构建最小生成树
	for(int i = 0 ; i < arr.size() ; i++)
	{	
		int x = arr[i].x; // [40] 获取当前道路的起点村庄编号
		int y = arr[i].y; // [41] 获取当前道路的终点村庄编号
		int a = arr[i].value; // [42] 获取当前道路的修建费用
		// [43] 调用find函数判断两个村庄是否已连通
		if(find(x) == find(y)) continue; // [44] 若已连通，跳过当前道路，避免生成环
		// [45] 调用unite函数合并两个村庄所在的连通集合
		unite(x , y);
		sum += a; // [46] 累加当前道路的修建费用到总费用
	}
	cout <<  sum; // [47] 输出所有村庄连通所需的最小修建总费用
    return 0; // [48] 主函数正常结束
}