问题 CE: Constructing Roads
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：40
解决：26
题目描述
有n个村庄，编号从1到n，要修建一些道路，使得每两个村庄都可以互相连通。若两个村庄a和b是连通的，当且仅当a和b之间有一条路，或者存在一个村庄c，使得a和c之间有一条路，并且c和b之间也有一条路。 我们知道在一些村庄之间已经有一些道路，现在的工作是修建一些道路，使得所有村庄都是连通的，并且所修建的道路长度最小。
输入
第一行是一个整数n(3<=n<=100)，这是村庄的数目。然后是n行，其中第i行包含n个整数，其中第j个整数表示i村和j村之间的距离（该距离为[1,1000]范围内的整数）。接着是一个整数Q(0<=Q<=n*(n+1)/2)。最后是Q行，每行包含两个整数a和b(1<=a<b<=n)，这意味着a村和b村之间的道路已经建成。
输出
输出一个整数，该整数是要修建的所有道路的长度，使得连通所有村庄，并且该值是最小值。
样例输入 复制
3
0 990 692
990 0 179
692 179 0
1
1 2
样例输出 复制
179