该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在遥远的“星港联邦”中，星港之间由大量稳定虫洞航道连接。每条航道的通过时间是固定的。
但航道维护成本高昂，联邦希望清理一部分“可有可无”的航道，以降低维护费用。

联邦的要求非常苛刻：清理后，星港之间的最短通行时间必须完全不变，并且整个星港网络仍需保持互相可达（连通）。

共有 $N$ 个星港，编号为 $1\sim N$。星港之间有 $M$ 条无向虫洞航道，第 $i$ 条连接星港 $u_i, v_i$，通过时间为 $w_i$（正整数）。保证图连通，且任意两星港之间最多只有一条航道（简单图）。

你可以删除若干条航道。删除后必须同时满足：

1. 网络仍然连通（任意两星港之间都存在路径）。
2. 对任意星港对 $(x,y)$，删除前后的最短通行时间完全相同。

请你计算：最多可以删除多少条航道。

输入格式

第一行两个整数 $N, M$。
接下来 $M$ 行，每行三个整数 $u_i, v_i, w_i$，表示一条无向航道。

输出格式

输出一个整数，表示最多可以删除的航道条数。

输入输出样例

4 5
1 2 2
2 3 2
3 4 2
1 4 6
1 3 4

2

3 3
1 2 5
2 3 1
1 3 10

1

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

0

数据范围与约定

• $2 \le N \le 300$
• $1 \le M \le \dfrac{N(N-1)}{2}$
• $1 \le w_i \le 10^9$
• 输入保证：无重边、无自环、图连通。
• 结果保证在 32 位有符号整数范围内。

测试点设计（共20点）

测试点编号	规模与特点
1-5	$N\le 12,\ M\le 25$
6-20	无约束