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: def main():
      import sys
  
      input = sys.stdin.readline
      sys.setrecursionlimit(10**7)
      from collections import Counter, deque
  
      # from collections import defaultdict
      from itertools import combinations, permutations, accumulate, groupby
  
      # from itertools import product
      from bisect import bisect_left, bisect_right
      from heapq import heapify, heappop, heappush
      from math import floor, ceil
  
      # from operator import itemgetter
  
      # inf = 10**17
      # mod = 10**9 + 7
  
      inf = 10**17
  
      def dijkstra_heap(start, edge):
          # 始点から各頂点への最短距離(頂点番号:0~N-1)
          d = [inf] * N
          used = [False] * N
          d[start] = 0
          used[start] = True
          edgelist = []
          # a:重み(//), b:次の頂点(%)
          for a, b, i in edge[start]:
              heappush(edgelist, (a * (10**6) + b, i))
  
          while len(edgelist):
              # まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
              minedge, i = heappop(edgelist)
              if used[minedge % (10**6)]:
                  continue
              node = minedge % (10**6)
              d[node] = minedge // (10**6)
              res[i] = 1
              used[node] = True
  
              for e in edge[node]:
                  if not used[e[1]]:
                      heappush(edgelist, ((e[0] + d[node]) * (10**6) + e[1], e[2]))
          return d
  
      # N:頂点数   W:辺数
      N, W = map(int, input().split())
      edge = [[] for i in range(N)]
      # edge[i] : iから出る道の[重み,行先]の配列
      for i in range(W):
          x, y, z = map(int, input().split())
          edge[x - 1].append((z, y - 1, i))
          edge[y - 1].append((z, x - 1, i))
  
      res = [0] * W
      for i in range(N):
          d = dijkstra_heap(i, edge)
      print(W - sum(res))
  
  
  if __name__ == "__main__":
      main()
  
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."}]