有N个乡村，编号从1到N，需要建立一些道路，保证任何两个乡村之间都是互通的。我们说两个乡村A和B是相连的，当A和B之间有一条路或者存在乡村C，A和C之间有路，C和B也是相连的。
我们知道一些乡村之间已经存在一些道路了，你的工作就是建立一些道路保证所有的乡村都是相连的，并且所有道路的长度是最小的。

第一行是个整数N(3 <= N <= 100),是乡村的个数。然后是N行，每行包含N个数字，第i行j列的数字表示第i个乡村和第j个乡村之间的距离。
接下来有个整数Q(0 <= Q <= N * (N + 1) / 2)。接下来有Q行，每行包含两个整数a和b (1 <= a < b <= N),表示乡村a和b之间的道路已经建好了。

你应该输出一行，包含一个整数，表示需要建的道路的长度和，保证所有乡村相连，并且该值最小。