この問題はいくつかの方針が考えられると思います。実際にいくつかの辺を削除したグラフで最短路を計算するのを繰り返す方針も考えられると思いますが、おそらくその方針では \(N^4\) オーダーの計算量になってしまうと考えられます。

この問題では「ある辺を残すかどうかを簡潔な条件で表す」という方針が正解への道筋です。この方針が見えなかった人は、試しに手元のメモにいくつかグラフを書いて実験してみて、どのような条件のときに辺を残す必要があるかを考えてみるとよいかもしれません。

さて、辺 \(i\) を残す条件は次のように表せます。

• \(A_i\) と \(B_i\) の距離が \(C_i\) であり、かつ
• 削除前のグラフにおいて、\(A_i\) と \(B_i\) を結ぶ \(2\) 本以上の辺を使った長さ \(C_i\) のパスが存在しない。

以下で証明していきましょう。
まず、辺 \(i\) が上の条件を満たすときに辺 \(i\) を取り除くと、\(A_i\) \(B_i\) 間の距離は \(C_i\) より大きくなってしまいます。よって辺 \(i\) は残す必要があります。
この問題は削除する辺の本数の最大値を求める問題だったので、これで「最大 \(M\) - (残す必要がある辺の本数) 本しか削除できない」という上界が示されました。
次に、残す必要がある辺のみを残してそれ以外の辺を削除したグラフ \(G'\) を考えましょう。このとき \(G'\) は問題文の条件を満たすことを証明できれば上界を達成できるグラフの存在を確認できるので、これを示します。
削除前のグラフにおいて、任意の頂点 \(u,v\) について頂点 \((u,v)\) 間の最短パスを \(1\) 本選び \(p_{u,v}\) とします。(ここで最短パスが複数ある場合は辺数が最も多いものから \(1\) 本選びます。)
\(p_{u,v}\) の辺数が \(1\) 本の場合、\(G'\) 上においても \(u,v\) 間の距離は \(p_{u,v}\) の長さに一致します。なぜなら \(u,v\) 間の辺は残されるからです。
\(p_{u,v}\) の辺数が \(k\) \((k \geq 2)\) 本だった場合は、ある頂点\(w\) が存在して、\(p_{uv}\)を \(uw\) パスと \(wv\) パスに分割できます。このとき \(p_{u,w}\) と \(p_{w,v}\) の辺数は \(k-1\) 本以下となるので、帰納法により \(G'\) 上においても \(u,v\) 間の距離は \(p_{u,v}\) の長さに一致することが確認できます。
以上より \(G'\) が問題文の条件を満たすことが確認できました。

よってこの問題は、任意の \(2\) 頂点 \(u, v\) 間の距離を計算できれば、辺 \(i\) を残すべきかどうかを高速に判定できることが分かりました。この計算はワーシャルフロイド法で \(\mathrm{O}(N^3)\) で行うことができます。よってこの問題を \(\mathrm{O}(N^3)\) で解くことができました。

Python での実装例は次の通りです。(処理系に PyPy3 を使用する必要があります。)

N, M = map(int, input().split())
es = []
inf = 10**18
for _ in range(M):
  a, b, c = map(int, input().split())
  es.append((a - 1, b - 1, c))

d = [[inf] * N for _ in range(N)]
for a, b, c in es:
  d[a][b] = c
  d[b][a] = c
for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

answer = 0
for a, b, c in es:
  unused = 0
  for i in range(N):
    if d[a][i] + d[i][b] <= c:
      unused = 1
  answer += unused
print(answer)