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: # 2020-05-28 22:26:38
  import sys
  
  sys.setrecursionlimit(10**8)
  input = sys.stdin.readline
  
  N, M = map(int, input().split())
  
  
  def modify(x, y):
      if x > y:
          x, y = y, x
      return (x, y)
  
  
  edge = [[] for _ in range(N)]
  edgeid = dict()
  for k in range(M):
      u, v, r = map(int, input().split())
      edge[u - 1].append((v - 1, r))
      edge[v - 1].append((u - 1, r))
      edgeid[modify(u - 1, v - 1)] = k
  
  from heapq import heappop, heappush, heapify
  
  INF = 10**20
  
  
  def dijkstra2(S, N, Edge):
      # S: start vertex
      # N: number of vertices
      # Edge: adjacent list [node, cost]
  
      dist = [INF] * N
      dist[S] = 0
      root = [-1] * N
      que = [(0, S)]
      heapify(que)
  
      while que:
          c, v = heappop(que)
          if dist[v] < c:
              continue
  
          for nv, nc in Edge[v]:
              if c + nc < dist[nv]:
                  dist[nv] = c + nc
                  root[nv] = v
                  heappush(que, (c + nc, nv))
  
      return [dist, root]
  
  
  def find_path(S, T, root):
      # SからTへのパスを逆順で返す
      path = []
      cur = T
      while cur != S:
          past = root[cur]
          path.append((past, cur))
          cur = past
      return path
  
  
  unused_flag = [True] * M
  for start in range(N):
      dist, root = dijkstra2(start, N, edge)
      for goal in range(N):
          if start == goal:
              continue
          for p in find_path(start, goal, root):
              unused_flag[edgeid[modify(p[0], p[1])]] = False
  
  print(sum(unused_flag))
  
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."}]