{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"Flatopia岛国是一个完全平坦的国家。不幸的是,Flatopia没有公共高速公路。因此,Flatopia的交通十分困难。Flatopia政府意识到了这个问题。他们计划修建一些高速公路,以便可以在不离开高速公路系统的情况下驾驶到任意两个城镇之间。 \n\n\u003cbr\u003e \n\n\u003cbr\u003eFlatopia的城镇编号从1到N。每条高速公路连接两个城镇。所有高速公路都是直线。所有高速公路可以双向使用。高速公路可以自由交叉,但驾驶员只能在位于两条高速公路末端的城镇之间切换高速公路。 \n\n\u003cbr\u003e \n\n\u003cbr\u003eFlatopia政府希望最小化要修建的最长高速公路的长度。但是,他们希望保证每个城镇都可以从其他每个城镇到达。"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行是一个整数T,表示后面有多少个测试用例。 \n\n\u003cbr\u003e \n\n每个案例的第一行是一个整数N(3 \u003c\u003d N \u003c\u003d 500),表示村庄的数量。然后是N行,其中第i行包含N个整数,第j个整数是村庄i和村庄j之间的距离(距离应为[1, 65536]范围内的整数)。每个测试用例之后都有一个空行。"}},{"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\u003e1\r\n\r\n3\r\n0 990 692\r\n990 0 179\r\n692 179 0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e692\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"输入量大,建议使用scanf。"}}]}