最短路

题目描述 有一个�个点的无向正权图�，这个图是连通的，你知道了这些点两两之间的最短 路的长度。

你想要构造一个新的无向正权图�'，使得新图中两两之间的最短路的长度与原图一 样，并且边数最少。

问最少的边数。

输入格式 第一行一个整数�，表示点的个数。

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

输出格式 一个整数表示新图�'的最小的边数。

样例输入 1 4 0 1 3 6 1 0 2 5 3 2 0 3 6 5 3 0

样例输出 1 3

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点 1 满足� ≤ 5。

测试点 2,3 满足� ≤ 15。

测试点 4,5,6 满足� ≤ 50。

对于所有数据，满足 1 ≤ � ≤ 300，保证图�中最短路长度不超过109 。