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: class Dijkstra:  # 最短経路問題
      def __init__(self, route_map, start_point, goal_point=None):
          self.route_map = route_map  #
          self.start_point = start_point  # スタート位置
          self.goal_point = goal_point
  
      def execute(self):
          import heapq
  
          num_of_city = len(self.route_map)  # ノード数
          dist = [float("inf") for _ in range(num_of_city)]  # startからの距離を格納する
          prev = [
              float("inf") for _ in range(num_of_city)
          ]  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
  
          dist[self.start_point] = 0  # スタート位置までのコストは0
          heap_q = []  # 優先度つきキュー
          heapq.heappush(
              heap_q, (0, self.start_point)
          )  # タプル(0,スタート位置)をheap_qに追加
          while len(heap_q) != 0:
              prev_cost, src = heapq.heappop(
                  heap_q
              )  # 直前にheap_qに入れたタプルから取り出す(src＝ソース)
  
              if (
                  dist[src] < prev_cost
              ):  # もし、スタート位置からsrcまでの距離がprev_costより小さいなら問題ないのでok
                  continue
  
              for dest, cost in self.route_map[
                  src
              ].items():  # destはsrcから行ける頂点(目的地)
                  if (
                      cost != float("inf") and dist[dest] > dist[src] + cost
                  ):  # もし、destに有限のコストで行けて、srcからdestに行くのがスタートからの現状の最短距離になるなら、
                      dist[dest] = dist[src] + cost  # 更新する
                      heapq.heappush(
                          heap_q, (dist[dest], dest)
                      )  # 更新したのでheap_qに入れておく。次のノードに移動した時に取り出して無駄な変更がないか確認する
                      prev[dest] = src
          if self.goal_point is not None:  # ゴールまでの最短経路を返す
              return self.get_path(self.goal_point, prev)
          else:  # スタートから各頂点までの最短距離を格納したリストを返す
              return dist
  
      def get_path(
          self, goal, prev
      ):  # prev[i]:ノードiに向かう前のノード番号。これを持っておけば、goalからstartまで辿れる
          global edge_num
          global used_edge
          path = [goal]
          dest = goal
  
          while prev[dest] != float("inf"):  # prev[start]はfloat("inf")になり、停止する
              used_edge[edge_num[prev[dest]][dest]] += 1
              path.append(prev[dest])  # 後ろから戻っていく
              dest = prev[dest]
  
          return list(reversed(path))  # 逆から辿ったので順を元に戻す
  
  
  import sys
  
  input = sys.stdin.readline
  
  
  N, M = map(int, input().split())
  route_map = [dict() for _ in range(N)]
  edge_num = [dict() for _ in range(N)]
  for i in range(M):  # M == エッジの数
      u, v, cost = map(int, input().split())  # cost は 辺　u -> v の重み(距離,コスト)
      u, v = u - 1, v - 1
      route_map[u][v] = cost  # route_mapの第u番目のdictに{v:cost}が入る
      route_map[v][u] = cost  # route_mapの第v番目のdictに{u:cost}が入る
      edge_num[u][v] = i  # redge_numの第u番目のdictに{v:i}が入る
      edge_num[v][u] = i  # redge_numの第v番目のdictに{u:i}が入る
  
  
  used_edge = [0 for _ in range(M)]
  checked_node = [[0 or _ in range(N)] for __ in range(N)]
  for i in range(N - 1):
      for j in range(i + 1, N):
          if checked_node[i][j] != 0:
              continue
          dijkstra_result1 = Dijkstra(route_map, i, j).execute()
          dijkstra_result2 = Dijkstra(route_map, N - 1 - i, N - 1 - j).execute()
          for k in range(len(dijkstra_result1) - 1):
              for l in range(k + 1, len(dijkstra_result1)):
                  checked_node[dijkstra_result1[k]][dijkstra_result1[l]] += 1
          for k in range(len(dijkstra_result2) - 1):
              for l in range(k + 1, len(dijkstra_result2)):
                  checked_node[dijkstra_result2[k]][dijkstra_result2[l]] += 1
  
  ans = used_edge.count(0)
  print(ans)
  
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."}]