题目描述

$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$

输出格式

答えを出力せよ。

题目大意

给你一张无重边无自环的联通带权无向图、

定义 $d(i,j)$ 是 $i$ 到 $j$ 的最短路径上的边权之和。

你需要删除一些边。要求删完之后的图满足下列条件：

• 图仍然联通；
• 对于 $1\le i,j\le N$，删边前的 $d(i,j)$ 等于删边后的 $d(i,j)$。

现在问你最多能删多少条边。

数据保证：

• $2\le N\le 300$
• $N-1\le M\le \frac{N(N-1)}{2}$
• $1\le u< v\le N$
• $1\le w\le 10^9$
• 图是联通的，没有重边和自环。

3 3
1 2 2
2 3 3
1 3 6

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$ 頂点 $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)$ である。
• 与えられるグラフは連結である。
• 入力はすべて整数である。

Sample Explanation 1

辺を削除する前の全ての頂点対の距離は次の通りです。 - 頂点 $1$ と頂点 $2$ の距離は $2$ - 頂点 $1$ と頂点 $3$ の距離は $5$ - 頂点 $2$ と頂点 $3$ の距離は $3$ 辺 $3$ を削除しても全ての頂点間の距離は変化しません。また、問題文の条件を満たすように $2$ 本以上の辺を削除することはできないので、答えは $1$ 本になります。

Sample Explanation 2

どの辺も削除することができません。