AT_abc243_e [ABC243E] Edge Deletion

给定一个有 $N$ 个顶点、$M$ 条边的简单连通无向图。 第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，长度为 $C_i$。 请删除若干条边，使得满足以下条件。请你求出最多可以删除多少条边。 - 删除边后，图仍然是连通的。 - 对于所有顶点对 $(s, t)$，删除前后顶点 $s$ 和顶点 $t$ 之间的距离不变。

输入以如下格式从标准输入给出。 > $N$ $M$ > $A_1$ $B_1$ $C_1$ > $A_2$ $B_2$ $C_2$ > $\vdots$ > $A_M$ $B_M$ $C_M$

请输出答案。

## 注释 简单连通无向图是指既简单又连通且边无方向的图。 图是简单的，意味着图中没有自环和重边。 图是连通的，意味着对于图中任意两个顶点 $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 < B_i \leq N$ - $1 \leq C_i \leq 10^9$ - 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$。 - 给定的图是连通的。 - 所有输入均为整数。 ## 样例解释 1 删除边之前，所有顶点对之间的距离如下： - 顶点 $1$ 和顶点 $2$ 之间的距离为 $2$ - 顶点 $1$ 和顶点 $3$ 之间的距离为 $5$ - 顶点 $2$ 和顶点 $3$ 之间的距离为 $3$ 即使删除第 $3$ 条边，所有顶点对之间的距离都不会改变。此外，无法再删除多于 $1$ 条边而满足题意，因此答案为 $1$。 ## 样例解释 2 无法删除任何一条边。 由 ChatGPT 4.1 翻译