题目描述：平坦国度修公路

平坦国度($Flatopia$)是一个完全平坦的岛国。不幸的是，这里没有高速公路，交通十分不便。政府决定修建高速公路，使得任意两个城镇之间都能通过高速公路互通。

城镇编号从$1$到$N$。每条高速公路连接两个城镇，笔直延伸，可双向通行。高速公路可以交叉，但只能在城镇处换乘。

政府希望在保证所有城镇连通的前提下，最小化最长高速公路的长度。

输入格式

• 第一行：测试用例数 $T$
• 每个测试用例：
  • 第一行：城镇数量 $N (3 ≤ N ≤ 500)$
  • 接下来$N$行：$N×N$的距离矩阵（第$i$行第$j$列表示城镇$i$到$j$的距离，距离为$[1, 65536]$的整数）
  • 每个测试用例后有一个空行

输出格式

• 对每个测试用例，输出一个整数，表示满足条件的最长公路的最小长度

输入输出样例（可直接复制）

输入样例 1

1

3
0 990 692
990 0 179
692 179 0

输出样例 1

692

解题提示

建议使用$scanf$提高读取效率

来源

POJ竞赛，作者：Mathematica@ZSU