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():
      def dijkstra_back(s, t):
          prev = [s] * n
          d = [float("inf")] * n
          used = [False] * n
          d[s] = 0
          while True:
              v = -1
              for i in range(n):
                  if (not used[i]) and (v == -1):
                      v = i
                  elif (not used[i]) and d[i] < d[v]:
                      v = i
              if v == -1:
                  break
              used[v] = True
              for i in range(n):
                  if d[i] > d[v] + cost[v][i]:
                      d[i] = d[v] + cost[v][i]
                      prev[i] = v
          path = [t]
          while prev[t] != s:
              path.append(prev[t])
              prev[t] = prev[prev[t]]
          path.append(s)
          path = path[::-1]
          return path
  
      n, m = map(int, input().split())
      route = [tuple(map(int, input().split())) for _ in range(m)]
      INF = float("inf")
      cost = [[INF for i in range(n)] for i in range(n)]
      for i in route:
          cost[i[0] - 1][i[1] - 1] = i[2]
          cost[i[1] - 1][i[0] - 1] = i[2]
  
      used_ways = set([])
      for i in range(n):
          for j in range(n):
              if i < j:
                  way = dijkstra_back(i, j)
                  for k in range(len(way) - 1):
                      used_ways.add(tuple(sorted([way[k], way[k + 1]])))
      route_set = set([])
      for i in route:
          route_set.add(tuple(sorted([i[0] - 1, i[1] - 1])))
      print(len(route_set - used_ways))
  
  
  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."}]