题目描述

给你一张无重边无自环的联通带权无向图、

定义 $d(i,j)$ 是 $i$ 到 $j$ 的最短路径上的边权之和。

你需要删除一些边。要求删完之后的图满足下列条件：

• 图仍然联通；
• 对于 $1\le i,j\le N$，删边前的 $d(i,j)$ 等于删边后的 $d(i,j)$。

现在问你最多能删多少条边。

输入格式

第一行输入两个整数 $N$ $M$

接下来 $M$ 行每行三个整数 $A_i$ $B_i$ $C_i$

输出格式

输出一个整数代表答案。

3 3
1 2 2
2 3 3
1 3 6

1

5 4
1 3 3
2 3 9
3 5 3
4 5 3

0

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

5

Sample Explanation 1

删除前每对顶点之间的距离如下。

• 顶点 $1$ 与顶点 $2$ 之间的距离为 $2$ 。
• 顶点 $1$ 与顶点 $3$ 之间的距离为 $5$ 。
• 顶点 $2$ 与顶点 $3$ 之间的距离是 $3$ 。

删除边 $3$ 不会影响任何一对顶点之间的距离。不可能在满足条件的情况下删除两条或两条以上的边，因此答案为 $1$ 。

提示

• $2\le N\le 300$
• $N-1\le M\le \frac{N(N-1)}{2}$
• $1\le u< v\le N$
• $1\le w\le 10^9$
• 图是联通的，没有重边和自环。