{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"有N个村庄,从1到N,你应该修建一些道路,这样每两个村庄就可以连接起来。我们说两个村庄A和B相连,当且仅当A和B之间有一条路,或者存在一个村庄C使得A和C之间有一条路,并且C和B相连。我们知道一些村庄之间已经有一些道路了,你的工作是修建一些道路,这样所有的村庄都连接起来,所有道路的长度都是最小的。"}},{"title":"Input","value":{"format":"HTML","content":"第一行是整数N (3 \u003c\u003d N \u003c\u003d 100),即村庄数。然后是N行,第i行包含N个整数,第j列是村i和村j之间的距离(距离应该是[1,1000]内的整数)。然后是整数Q (0 \u003c\u003d Q \u003c\u003d N * (N + 1) / 2),然后是Q行,每一行包含两个整数a和b (1 \u003c\u003d a \u003c b \u003c\u003d N),这意味着a村和b村之间的道路已经建成。"}},{"title":"Output","value":{"format":"HTML","content":"您应该输出一条包含整数的线,该整数是所有要修建的道路的长度,以便所有村庄都连接起来,并且该值是最小的。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3\n0 990 692\n990 0 179\n692 179 0\n1\n1 2\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e179\u003c/pre\u003e"}}]}