公路（最小生成树）

描述

岛屿国家Flatopia是完全平坦的。不幸的是，Flatopia没有公共的公路。所以Flatopia的交通很困难。Flatopian政府意识到这个问题。他们正在计划修建一些高速公路，这样就可以在任何一个城镇之间行驶，而不必离开公路系统。

每个高速公路连接两个城镇。所有高速公路都沿着直线。所有高速公路都可以在两个方向上使用。高速公路可以自由交叉，但驾驶员只能在位于两条高速公路末端的小镇的高速公路之间切换。

Flatopian政府希望减少最长的高速公路的长度。但是，他们希望保证每个城镇都可以从其他城镇进入高速公路。

输入

输入的第一行是一个整数T，它告诉后面有多少个测试用例。

每种情况的第一行是一个整数N（3 <= N <= 500），这是村庄的数量。然后来N行，其中第i个包含N个整数，这N个整数中的第j个是村i和村j之间的距离（距离应该是[1 65536]内的整数）。每个测试用例后都有一个空行。

产量

对于每个测试用例，应该输出一个包含整数的行，这个长度是所有村庄连接的最长路径的长度，这个值是最小的。

示例输入

1

3

0 990 692

990 0 179

692 179 0

示例输出

692

题意：

给图的邻接矩阵，求最小生成树，输出树的最大边

题解：

保存每次边的权值，最后遍历一次或使用sort排序得到最大边