题目描述

给定一个简单连通无向图，有 $N$ 个顶点和 $M$ 条边。
第 $i$ 条边连接了顶点 $A_i$ 和顶点 $B_i$，并且边的长度为 $C_i$。

在满足以下条件的情况下删除一些边，请找到最大可以删除的边数。

• 删除后图依然是连通的。
• 对于每对顶点 $(s, t)$，删除前后 $s$ 和 $t$ 之间的距离保持不变。

注意事项

简单连通无向图是指一个简单的、连通的，并且带有无向边的图。
当图中不存在自环和重边时，称其为简单图。
当对于任意一对顶点 $s$ 和 $t$，可以通过遍历边从 $s$ 到达 $t$ 时，称图是连通的。
顶点 $s$ 和顶点 $t$ 之间的距离是 $s$ 和 $t$ 之间的最短路径的长度。

约束条件

• $2 \leq N \leq 300$
• $N-1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i \lt B_i \leq N$
• $1 \leq C_i \leq 10^9$
• 如果 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$。
• 给定的图是连通的。
• 输入中的所有值都是整数。

输入

从标准输入读入数据，输入格式如下：

$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$

输出

输出答案。

示例输入1

3 3
1 2 2
2 3 3
1 3 6

示例输出1

1

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

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

删除边 $3$ 不会影响任意一对顶点之间的距离。不可能满足条件同时删除两条或更多的边，因此答案是 $1$。

示例输入2

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

示例输出2

0

无法删除任何边。

示例输入3

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

示例输出3

5