This problem has several ways to solve. One may consider repeating actually finding the shortest path on a graph after several edges are removed, but probably that algorithm costs an order of \(N^4\).

In this problem, an effective approach for the correct answer is “to represent whether an edge should be retained by simple conditions.” If you didn’t come up with this approach, it may be useful to try drawing some graphs to consider in what condition the edges should be retained.

Edge \(i\) should not be removed if:

• the distance between \(A_i\) and \(B_i\) is \(C_i\), and
• before the edges are removed, there is no path connecting \(A_i\) and \(B_i\) of length \(C_i\) consisting of two or more edges.

We will explain the details.
First, if Edge \(i\) satisfies the conditions above, by removing Edge \(i\) the distance between \(A_i\) and \(B_i\) becomes larger than \(C_i\). Therefore, Edge \(i\) should not be removed.
Since we are asked to find the maximum number of edges to be removed in this problem, we have now find the upper bound: at most, we can remove (\(M\) - (the number of edges that should be retained)) edges.
Next, let’s consider the graph \(G'\) in which all the edges that can be removed are removed and all the edges that should be preserved are retained. If we could prove that \(G'\) satisfies the condition in the Problem Statement, then we can check the existence of the graph achieving the upper bound, so we will prove that.
Before removing, for some pair of vertices \(u\) and \(v\), let \(p_{u,v}\) be the one of the shortest paths between Vertices \(u\) and \(v\). (If there are multiple shortest paths, we choose one with the most number of edges.)
If \(p_{u,v}\) contains a single edge, then distance between \(u\) and \(v\) on \(G'\) is equal to the length of \(p_{u,v}\), because the edge between \(u\) and \(v\) remains.
If \(p_{u,v}\) has \(k\) \((k \geq 2)\) edges, then there exists a vertex \(w\) so that \(p_{u,v}\) is divided into \(uw\)-path and \(wv\)-path. Then, the number of edges of \(p_{u,w}\) and \(p_{w,v}\) are both less than or equal to \(k-1\), so by induction we can assert that the distance between \(u\) and \(v\) is equal to the length of \(p_{u,v}\).
Therefore, \(G'\) satisfies the condition in the Problem Statement.

Therefore, this problem can be solved if we could find the distance between all pair of vertices \((u, v)\), because we can then check if Edge \(i\) should be retained fast enough. This computation can be done with Floyd-Warshall Algorithm in a total of \(\mathrm{O}(N^3)\) time. Therefore, this problem could be solved in a total of \(\mathrm{O}(N^3)\) time.

Here is a sample code in Python. (You have to choose PyPy3 as the processing system.)

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)