output_description: Print the number of the edges in the graph that are not contained in any
  shortest path between any pair of different vertices.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M  
      a_1 b_1 c_1  
      a_2 b_2 c_2
      :  
      a_M b_M c_M
attempt: N, M = map(int, input().split())
  ABC = []
  for i in range(M):
      abc = tuple(map(int, input().split()))
      ABC.append(abc)
  
  # print(N, M, ABC)
  
  max_len = 0
  for abc in ABC:
      max_len += abc[2]
  
  
  def sub(a, b, d, d_min, ABC, path):
      # print('sub', a, b, d, d_min, ABC, path)
      for abc in ABC:
          # print('sub', abc)
          if abc[0] == a:
              n_a = abc[1]
              tmp_d = d + abc[2]
              if tmp_d > d_min:
                  # print('exceed', d, d_min)
                  continue
              if n_a == b:
                  path.append(n_a)
                  # print('found', tmp_d, path)
                  return tmp_d
              tmp = [x for x in path]
              tmp.append(n_a)
              tmp_d = sub(n_a, b, tmp_d, d_min, ABC, tmp)
              if tmp_d > d_min:
                  # print('exceed2', tmp_d, d_min)
                  continue
          if abc[1] == a:
              n_a = abc[0]
              tmp_d = d + abc[2]
              if tmp_d > d_min:
                  # print('exceed', tmp_d, d_min)
                  continue
              if n_a == b:
                  path.append(n_a)
                  # print('found', tmp_d, path)
                  return tmp_d
              tmp = [x for x in path]
              tmp.append(n_a)
              tmp_d = sub(n_a, b, tmp_d, d_min, ABC, tmp)
              if tmp_d > d_min:
                  # print('exceed2', tmp_d, d_min)
                  continue
      # print('not found')
      path = []
      return max_len
  
  
  def shortest(a, b, ABC):
      d_min = max_len
      ans = []
      for abc in ABC:
          # print('shortest', a, b, abc)
          if abc[0] == a:
              n_a = abc[1]
              d = abc[2]
              path = [a, n_a]
              if n_a == b and d <= d_min:
                  d_min = d
                  ans = [path]
                  continue
              d = sub(n_a, b, d, d_min, ABC, path)
              if d <= d_min:
                  # print('shortest, found', d, path)
                  d_min = d
                  ans = [path]
              if d == d_min:
                  ans.append(path)
          if abc[1] == a:
              n_a = abc[0]
              d = abc[2]
              path = [a, n_a]
              if n_a == b and d <= d_min:
                  d_min = d
                  ans = [path]
                  continue
              d = sub(n_a, b, d, d_min, ABC, path)
              if d < d_min:
                  # print('shortest, found', d, path)
                  d_min = d
                  ans = [path]
              if d == d_min:
                  ans.append(path)
      return ans
  
  
  # print(shortest(1, 2, ABC))
  # print(shortest(1, 3, ABC))
  # print(shortest(2, 3, ABC))
  
  s_paths = set()
  
  for i in range(N):
      for j in range(i + 1, N):
          paths = shortest(i + 1, j + 1, ABC)
          # print(i, j, paths)
          for path in paths:
              # print(path)
              for k in range(len(path) - 1):
                  l = min(path[k], path[k + 1])
                  r = max(path[k], path[k + 1])
                  s_paths.add((l, r))
  
  print(len(ABC) - len(s_paths))
  
problem_description: Statement
  
  You are given an undirected connected weighted graph with N vertices and M
  edges that contains neither self-loops nor double edges.  
  The i-th (1≤i≤M) edge connects vertex a_i and vertex b_i with a distance of
  c_i.  
  Here, a _self-loop_ is an edge where a_i = b_i (1≤i≤M), and _double edges_ are
  two edges where (a_i,b_i)=(a_j,b_j) or (a_i,b_i)=(b_j,a_j) (1≤i<j≤M).  
  A _connected graph_ is a graph where there is a path between every pair of
  different vertices.  
  Find the number of the edges that are not contained in any shortest path
  between any pair of different vertices.
samples: [{"input": "3 3\n    1 2 1\n    1 3 1\n    2 3 3", "output": "1\n    \n\nIn the given graph, the shortest paths between all pairs of different vertices\nare as follows:\n\n  * The shortest path from vertex 1 to vertex 2 is: vertex 1 \u2192 vertex 2, with the length of 1.\n  * The shortest path from vertex 1 to vertex 3 is: vertex 1 \u2192 vertex 3, with the length of 1.\n  * The shortest path from vertex 2 to vertex 1 is: vertex 2 \u2192 vertex 1, with the length of 1.\n  * The shortest path from vertex 2 to vertex 3 is: vertex 2 \u2192 vertex 1 \u2192 vertex 3, with the length of 2.\n  * The shortest path from vertex 3 to vertex 1 is: vertex 3 \u2192 vertex 1, with the length of 1.\n  * The shortest path from vertex 3 to vertex 2 is: vertex 3 \u2192 vertex 1 \u2192 vertex 2, with the length of 2.\n\nThus, the only edge that is not contained in any shortest path, is the edge of\nlength 3 connecting vertex 2 and vertex 3, hence the output should be 1.\n\n* * *"}, {"input": "3 2\n    1 2 1\n    2 3 1", "output": "0\n    \n\nEvery edge is contained in some shortest path between some pair of different\nvertices."}]