近两年xx大学要求各院系深入农村基层开展扶贫工作，今年我系的任务是去xx的A县进行扶贫，而计算机系师生希望通过技术解决一些实际的问题，目前A县有一个这样的问题希望你能给出解决方案，A县正在实施村村通工程，希望将各个村庄连接起来，目前A县有N(3<= N<=100)个村庄，编号为1,2.3..N，你需要给出一个方案，使得任意两个村子都可以连通并且总的路程最短，已知某些村子已经通了公路。
输入
输入包括多行
第一行包括一个数字N，表示村子的数目
接下来是 N行，每一行包括N个正整数，第行表示村子i到其它所有村子的距离下面一行包括一个数字M(k=M<=50)，表示已经修通的公路总数
接下来M行，每行包括两个整数表示已经连通的两个村庄编号
输出
输出最短距离
样例输入
0 600 400
680 8 120
408 128 0
12
样例输出
128