树的重量

题目描述

树可以用来表示物种之间的进化关系。一棵“进化树”是一个带边权的树,其叶节点表示一个物种,两个叶节点之间的距离表示两个物种的差异。现在,一个重要的问题是,根据物种之间的距离,重构相应的“进化树”。 令N={1..n},用一个N上的矩阵M来定义树T。其中,矩阵M满足:对于任意的i,j,k,有M[i,j] + M[j,k] >= M[i,k]。树T满足: 1.叶节点属于集合N; 2.边权均为非负整数; 3.dT(i,j)=M[i,j],其中dT(i,j)表示树上i到j的最短路径长度。 如下图,矩阵M描述了一棵树。 ![](https://cdn.luogu.com.cn/upload/pic/82.png) 树的重量是指树上所有边权之和。对于任意给出的合法矩阵M,它所能表示树的重量是惟一确定的,不可能找到两棵不同重量的树,它们都符合矩阵M。你的任务就是,根据给出的矩阵M,计算M所表示树的重量。下图是上面给出的矩阵M所能表示的一棵树,这棵树的总重量为15。 ![](https://cdn.luogu.com.cn/upload/pic/83.png)

输入输出格式

输入格式


输入数据包含若干组数据。每组数据的第一行是一个整数n(2

输出格式


对于每组输入,输出一行,一个整数,表示树的重量。

输入输出样例

输入样例 #1

5
5 9 12 8
8 11 7
5 1
4
4
15 36 60
31 55
36
0

输出样例 #1

15
71