在网络中，发送一个包需要知道对方的物理地址。当不知道物理地址的时候，就要向网络中广播发送对方的 IP 地址，然后每一台计算机都会收到这个广播，如果 IP 和自己的计算对上了，就把自己的物理地址发送出去。
现在有 n 台计算机，编号从 1 到 n。现在 1 号计算机向网络中发送广播，问经过多少时间后所有的计算机都会收到这个广播。
输入的网络保证所有的计算机之间是可以相互通信的。信号沿着链路传播，一台计算机会在它最早能收到的时刻收到广播（即从 1 号到它的最短传播时间），因此所有计算机都收到的时刻就是“1 号到各点最短路距离的最大值”。

单组测试数据。
第1行：一个整数 n（1 <= n <= 100）。
接下来给出一个 n x n 邻接矩阵的下三角部分，共 n-1 行：第 i 行（对应第 i+1 台计算机）有 i 个元素，依次表示 A[i+1][1], A[i+1][2], ..., A[i+1][i]。元素要么是非负整数（表示该链路传播需要的时间），要么是字符 x（表示两台计算机没有直接相连）。矩阵对称（A[i][j]=A[j][i]），且 A[i][i]=0。

输出一个整数，表示所有计算机都收到广播所需的时间。

以 1 号为源点做单源最短路（Dijkstra），答案为源点到所有可达点最短路距离的最大值。注意只输入了下三角，读入时需对称地补上 a[j][i]=a[i][j]；x 表示无边。