农夫约翰被选为镇长！他的竞选承诺之一是将互联网连接到该地区的所有农场。当然，他需要你的帮助。 给出连接每对场所需光纤的列表，您必须找到将它们连接在一起所需的最低光纤数量。每个场必须连接到其他某个场，以便。数据包可以从任何一个场流向任何其他场。 任何两个农场之间的距离不超过100000。

输入包括几个案例。对于每种情况，第一行包含农场的数量N（3<=N<=100）。以下几行包含N x N矩阵，其中每个元素显示从农场到另一个农场的距离。它们是由N个空格分隔的整数组成的N行。对角线是0。

对于每种情况，输出一个整数长度，该长度是连接整套场所需的最小光纤长度的总和。