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: # https://atcoder.jp/contests/abc051/tasks/abc051_d
  # 考えたこと
  # 1.経路復元
  # 2.ダイクストラ時に使った辺記録(こっちで解いてみる)
  
  
  # あとで必要なのでクラスを準備しておく
  from heapq import heapify, heappop, heappush, heappushpop
  
  import sys
  
  sys.setrecursionlimit(1 << 25)
  read = sys.stdin.readline
  ra = range
  enu = enumerate
  
  
  def read_ints():
      return list(map(int, read().split()))
  
  
  class PriorityQueue:
      def __init__(self, heap):
          """
          heap ... list
          """
          self.heap = heap
          heapify(self.heap)
  
      def push(self, item):
          heappush(self.heap, item)
  
      def pop(self):
          return heappop(self.heap)
  
      def pushpop(self, item):
          return heappushpop(self.heap, item)
  
      def __call__(self):
          return self.heap
  
      def __len__(self):
          return len(self.heap)
  
  
  INF = 10**9 + 1
  
  
  def dijkstra(adj: list, s: int, N: int):
      Color = [0] * N  # 0:未訪問 1:訪問経験あり 2:訪問済み(そこまでの最短経路は確定済み)
      D = [INF] * N  # 本のdと同じ 始点からの距離を記録する
      P = [None] * N  # 本のpと同じ 最短経路木における親を記録する
  
      # スタートとするノードについて初期化
      D[s] = 0  # スタートまでの距離は必ず0
      P[s] = None  # 親がない(ROOTである)ことを示す
      PQ = PriorityQueue(
          [(0, s)]
      )  # (コスト, ノード番号)で格納 こうするとPQでソートするときに扱いやすい
  
      # while True:
      while PQ:  # PQに候補がある限り続ける
          # min_cost = INF
          # for i in range(N):
          #     if Color[i] != 2 and D[i] < min_cost:
          #         min_cost = D[i]
          #         u = i
          min_cost, u = PQ.pop()  # 上記の処理はこのように簡略化できる
  
          Color[u] = 2  # uは訪問済み これから最短経路木に突っ込む作業をする
  
          if D[u] < min_cost:
              # もし今扱っているmin_costがメモしているやつよりも大きいなら何もしないで次へ(メモしている方を扱えばいいので)
              continue
  
          # 以下のforではsからの最短経路木にuを追加したときの更新、uまわりで次の最短経路になる候補の更新をしている
          for idx_adj_u, w_adj_u in adj[u]:
              if Color[idx_adj_u] != 2:
                  # 訪問済みでなく、u→vへの経路が存在するならば
                  if D[u] + w_adj_u < D[idx_adj_u]:
                      D[idx_adj_u] = D[u] + w_adj_u  # u周りにおける最短経路の候補の更新
                      P[idx_adj_u] = u
                      PQ.push((D[idx_adj_u], idx_adj_u))  # ここで候補に追加していっている
                      Color[idx_adj_u] = 1
  
      return D, P
  
  
  # load datas
  N, M = read_ints()
  adj = [[] for _ in range(N)]  # (node_id, 隣接要素, 隣接nodeidとコスト)の順で格納する
  for _ in range(M):
      a, b, c = read_ints()
      a -= 1
      b -= 1
      adj[a].append((b, c))
      adj[b].append((a, c))
  
  used_edges = set()
  for s in range(N):
      _, P = dijkstra(adj, s, N)
      for i, p in enu(P):
          if p == None:
              continue
          if p > i:
              i, p = p, i
          used_edges.add((i, p))
  
  print(M - len(used_edges))
  
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."}]