删边

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图。

第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$,长度为 $C_i$。

在满足以下条件的范围内删除若干条边,求最多可以删除多少条边。

• 删除后,图仍然连通。
• 对于任意一对顶点 $(s, t)$,删除前后 $s$ 和 $t$ 之间的距离保持不变。

注

• 简单连通无向图是指简单、连通且具有无向边的图。
• 没有自环和重边的图称为简单图。
• 如果对于任意两个顶点 $s$ 和 $t$,都能通过若干条边从 $s$ 到达 $t$,则称该图是连通的。
• 顶点 $s$ 和顶点 $t$ 之间的距离是指 $s$ 和 $t$ 之间的最短路径的长度。

输入格式

输入按以下格式从标准输入给出:

N M
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_M B_M C_M

输出格式

输出答案。

样例

3 3
1 2 2
2 3 3
1 3 6

1

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

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

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

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

删除边 $3$ 不会影响任何一对顶点之间的距离。在满足条件的情况下不可能删除两条或更多条边,因此答案是 $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

数据范围

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