公路（最小生成樹）

描述

島嶼國家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排序得到最大邊