有一个 n 个点的无向正权图 G ，这个图是连通的，你知道了这些点两两之间的最短路的长度。
你想要构造一个新的无向正权图 G' ，使得新图中两两之间的最短路的长度与原图一样，并且边数最少。
问最少的边数。样例如图所示：

第一行一个整数 n ，表示点的个数。

接下来 n 行，每行 n 个整数。第 i 行第 j 个整数表示 i 点到 j 点的在 G 中的最短路长度，数据保证合法。

一个整数表示新图 G' 的最小的边数。

4
0 1 3 6
1 0 2 5
3 2 0 3
6 5 3 0

3

数据规模
共 10 个测试点。
测试点 1 满足 n≤ 5 。
测试点 2,3 满足 n≤ 15 。
测试点 4,5,6 满足 n≤ 50 。
对于所有数据，满足 1≤n≤300 ，保证图 G 中最短路长度不超过 10^9 。