AT_abc243_e [ABC243E] Edge Deletion

[problemUrl]: https://atcoder.jp/contests/abc243/tasks/abc243_e $ 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 $

答えを出力せよ。

### 注釈 単純連結無向グラフとは、単純かつ連結で辺に向きの無いグラフのことをいいます。 グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。 グラフが連結であるとは、グラフ上の任意の $ 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 どの辺も削除することができません。