当前没有测试数据。

E - 删除边

得分：500 分

问题描述

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

我们删除一些边，同时满足以下条件。求可以删除的最大边数。

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

注释

一个简单连通无向图是一个简单的连通且仅含一条无向边的图。
一个图是简单的当且仅当它没有自环和多边。
一个图是连通的当且仅当对于任意两个顶点 $s$ 和 $t$，通过边遍历，$t$ 可以从 $s$ 到达。
顶点 $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$

输出

输出答案。

---

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