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: # import numpy as np
  N, M = map(int, input().split())
  inf = 10**9
  
  
  class Node:
      def __init__(self, ix):
          self.ix = ix  # ノード番号
          self.done = False  # 確定ノードかどうか
          self.pay = {}  # 頂点番号:コストの一覧を容れる辞書
          self.paid = -1  # ここに到達するための最小コスト(未定義なら-1)
          self.prev = -1  # 最小コストを与える親ノード(未定義なら-1)
  
      def __str__(self):
          # デバッグ用
          return "{} <- [{}] <- {}, done:{}, pay:{}".format(
              self.ix, self.paid, self.prev, self.done, self.pay
          )
  
  
  # ノードのリストを生成
  nodes = []
  for i in range(N):
      nodes.append(Node(i))
  
  # エッジのリストを生成(これはこの問題用)
  # edges = np.zeros((N,N), dtype=np.uint8)
  edges = []
  for _ in range(N):
      edges.append([0] * N)
  
  # エッジ情報を取得
  # 全エッジを格納
  # 注意: 標準入力は1-indexedだがここでは0-indexedに直す
  for _ in range(M):
      a, b, c = map(int, input().split())
      nodes[a - 1].pay[b - 1] = c
      nodes[b - 1].pay[a - 1] = c
      edges[a - 1][b - 1] = 1
      edges[b - 1][a - 1] = 1
  
  
  # 出発ノードを0からN-1まで変化させる
  for i in range(N):
      ##### DEBUG
      # print('start node: {}'.format(i))
      nodes[i].prev = i  # 出発点の最良親を自分自身に
      nodes[i].paid = 0  # 出発点のコストは0
      nodes[i].done = True  # 出発点は確定済み
      n_done = 1  # 確定ノード数を1に
      while n_done < N:  # 全部確定するまで続行
          to_conf_ix = -1  # 次に確定されるべきノード番号
          to_conf_paid = 10**9  # そのコスト
          for node in nodes:
              # 確定ノードすべてに対して操作を行う
              if node.done:
                  ##### DEBUG
                  # print('confirmed parent: {}'.format(node.ix))
                  # 接続先を全列挙
                  for child in list(node.pay.keys()):
                      # その接続先が未確場合のみ進む定なら処理続行
                      if not nodes[child].done:
                          # その接続先の仮の最小コストと仮の親を更新
                          # まだ確定済みにはしない
                          newcost = node.paid + node.pay[child]
                          # 更新するための条件
                          flag = (nodes[child].paid < 0) or (newcost < nodes[child].paid)
                          ##### DEBUG
                          # print('p{} -> c{}, prevcost={}, newcost={}'.format(node.ix, child, nodes[child].paid, newcost))
                          # 条件をみたせば接続先の情報を更新
                          # また次に確定されるノード候補の情報も更新
                          if flag:
                              nodes[child].paid = newcost
                              nodes[child].prev = node.ix
                          if newcost < to_conf_paid:
                              to_conf_paid = newcost
                              to_conf_ix = child
                          ##### DEBUG
                          # print('to_conf: ix:{}, cost:{}'.format(to_conf_ix, to_conf_paid))
          # 操作が完了したら現段階の候補ノードを確定させる
          nodes[to_conf_ix].done = True
          # 確定ノード数を1増やす
          n_done += 1
          ##### DEBUG
          # print('--- n_done: {} ---'.format(n_done))
          # for j in range(N):
          # 	print(nodes[j])
          # print('------------------')
  
      # 各ノードについてそれを親と連結するパスをedgeから削除
      for j in range(N):
          k = nodes[j].prev
          edges[j][k], edges[k][j] = 0, 0
  
      # 全ノードのpaid,prevをリセット
      for j in range(N):
          nodes[j].paid, nodes[j].prev = -1, -1
          nodes[j].done = False
  
  # 最後にedgesに残っているエッジの本数を出力
  # print(int(np.sum(edges)//2)) # NumPy
  ans = 0
  for i in range(N):
      ans += sum(edges[i])
  print(ans // 2)
  
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."}]