有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之间已经修建了一条道路。

你应该输出一行，包含一个整数，表示修建所有道路使得所有村庄连接起来的最小总长度。