{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"有N个村庄,编号从1到N,你需要修建一些道路,使得每两个村庄都可以相互连接。我们说两个村庄A和B是连接的,当且仅当A和B之间有一条道路,或者存在一个村庄C,使得A和C之间有一条道路,且C和B是连接的。\n\n我们知道已经有一些村庄之间已经存在一些道路,你的任务是修建一些道路,使得所有村庄都连接起来,并且所修建的所有道路的长度之和最小。"}},{"title":"输入","value":{"format":"HTML","content":"第一行是一个整数N (3 \u003c\u003d N \u003c\u003d 100),表示村庄的数量。接下来是N行,第i行包含N个整数,其中第j个整数表示村庄i和村庄j之间的距离(距离应为一个在[1, 1000]范围内的整数)。\n\n然后是一个整数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":"输出","value":{"format":"HTML","content":"你应该输出一行,包含一个整数,表示修建所有道路使得所有村庄连接起来的最小总长度。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n0 990 692\r\n990 0 179\r\n692 179 0\r\n1\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e179\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}