Flatopia是个很平的地方，政府想要修高速公路，以解决交通问题。高速公路系统能使得驾驶能够不出离此系统就能够在任意两城之间通行。城镇编号1~N，每条高速路连接两个城镇，所有高速路都是直线的，双向使用的。但是一个驾驶员只能在公路的尽头的城镇改变线路。当地政府想要尽量减少所需修建最长公路的长度，然而，必须保证每一个城镇都是可以达到的。

输入：

处理情况。

由一个矩阵代表了每两个镇之间的距离，每个情况末尾是空行。



二、　　算法分析：

题目抽象后可得，给定一个图，要求找到一个可以让所有结点连接的方式，使得其中权值最大者最小。

-Flatopia is a very flat place, the government wants to repair the highway in order to solve the traffic problem.Highway system allows the driver to leave the system is not able to travel between any two cities.Town No. 1 ~ N, each highway connecting the two towns, all highways are straight, bi-directional use.But a driver can only be the end of the road to change the town line.The local government wants to minimize the build up to the required length of roads, however, to ensure every town is achievable.