{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":" A国没有高速公路,因此A国的交通很困难。政府意识到了这个问题并且计划建造一些高速公路,以至于可以在不离开高速公路的情况下在任意两座城镇之间行驶。\n\n A国的城镇编号为1到N, 每条高速公路连接这两个城镇,所有高速公路都可以在两个方向上使用。高速公路可以自由的相互交叉。\n\n A国政府希望尽量减少最长高速公路的建设时间(使建设的最长的高速公路最短),但是他们要保证每个城镇都可以通过高速公路到达任意一座城镇。\n"}},{"title":"Input","value":{"format":"MD","content":"第一个输入的数字T,代表着T组样例。\n\n接下来输入一个N, 代表一共有N个城镇(3 \u003c\u003d N \u003c\u003d 500)。\n\n然后读入一个N*N的矩阵,第i行第j列代表从i到j高速公路的距离( 1\u003c\u003d 距离 \u003c\u003d 65536)。"}},{"title":"Output","value":{"format":"MD","content":"对于每个测试用例,您应输出一个包含整数的行,该整数是要构建的最长道路的长度,以便连接所有村庄,并且此值最小。"}},{"title":"Sample Input","value":{"format":"MD","content":"1\n\n3\n0 990 692\n990 0 179\n692 179 0"}},{"title":"Sample Output","value":{"format":"MD","content":"692\n"}},{"title":"Hint","value":{"format":"MD","content":" Huge input,scanf is recommended."}}]}