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: from collections import deque
  
  sx, sy, tx, ty = map(int, input().split())
  ans_list = []
  (tx, ty) = (tx - sx, ty - sy)
  (sx, sy) = (0, 0)
  H, W = ty + 3, tx + 3
  visited = [[0] * (tx + 3) for i in range(ty + 3)]
  d = [[1, 0], [0, 1], [-1, 0], [0, -1]]
  (sx, sy) = (sx + 1, sy + 1)
  (tx, ty) = (tx + 1, ty + 1)
  
  
  def bfs(si, sj, gi, gj):
      tr = [[si, sj]]
      q = deque([[si, sj, tr]])
      while q:
          i, j, tr = q.popleft()
          if (i, j) == (gi, gj):
              return tr
          for di, dj in d:
              ni = i + di
              nj = j + dj
              if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and visited[ni][nj] == 0:
                  visited[ni][nj] = 1
                  ntr = tr[:]
                  ntr.append([ni, nj])
                  q.append([ni, nj, ntr])
  
  
  def change(tr):
      def func(d):
          if d == (1, 0):
              return "U"
          if d == (-1, 0):
              return "D"
          if d == (0, -1):
              return "L"
          if d == (0, 1):
              return "R"
  
      for i in range(len(tr) - 1):
          (ni, nj) = (tr[i + 1][0], tr[i + 1][1])
          (i, j) = (tr[i][0], tr[i][1])
          d = (ni - i, nj - j)
          ans_list.append(func(d))
  
  
  tr = []
  for cnt in range(2):
      res = bfs(sy, sx, ty, tx)
      for k in range(1, len(res)):
          i, j = res[k][0], res[k][1]
          rei, rej = ty + sx - i, tx + sy - j
          res.append([rei, rej])
      if cnt == 0:
          tr += res
      else:
          tr += res[1:]
      visited = [[0] * W for i in range(H)]
      for i, j in tr:
          visited[i][j] = 1
      visited[ty][tx] = 0
  
  change(tr)
  ans = "".join(ans_list)
  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."}]