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 DirectedEdge(object):
      def __init__(self, v, w, weight, id):
          self.v = v
          self.w = w
          self.weight = weight
          self.id = id
  
      def __str__(self):
          return "[{} -> {}: {}]".format(self.v, self.w, self.weight)
  
      def edge_from(self):
          return self.v
  
      def edge_to(self):
          return self.w
  
      def get_weight(self):
          return self.weight
  
      def get_id(self):
          return self.id
  
  
  class EdgeWeightedDigraph(object):
      def __init__(self, vertex_size):
          self.VERTEX_SIZE = vertex_size
          self.adj = [set() for x in range(self.get_vertex_size())]
  
      def get_vertex_size(self):
          return self.VERTEX_SIZE
  
      def add_edge(self, edge):
          v = edge.edge_from()
          self.adj[v].add(edge)
  
      def get_adj(self, v):
          res = set()
          for edge in self.adj[v]:
              res.add(edge)
          return res
  
  
  class IndexMinPQ(object):
      def __init__(self, size):
          self.keys = [None for x in range(size + 1)]  # key を格納
          self.pq = [
              None for x in range(size + 1)
          ]  # tree 構造を形成する. key の id を格納
  
          self.qp = [None for x in range(size + 1)]
  
          self.n = 0
  
      def contains(self, i):
          if self.qp[i] is None:
              return False
          else:
              return True
  
      def is_empty(self):
          return self.n == 0
  
      def size(self):
          return self.n
  
      def decrease_key(self, i, key):
          self.keys[i] = key
          self._swim(self.qp[i])
  
      def insert(self, i, key):
          tail = self.n + 1
          self.pq[tail] = i
          self.qp[i] = tail
          self.keys[i] = key
  
          self._swim(tail)
  
          self.n += 1
  
      def _swim(self, i):
          while i != 1:
              p = self._get_parent_pos(i)
              if not self._is_less(p, i):
                  self._exch(p, i)
                  i = p
              else:
                  break
  
      def del_min(self):
          head = self.pq[1]
  
          self.pq[1] = None
          self.keys[head] = None
          self.qp[head] = None
  
          self._exch(1, self.n)
  
          self.n -= 1
          self._sink(1)
  
          return head
  
      def _sink(self, i):
          while self._get_left_child_pos(i) <= self.n:
              left = self._get_left_child_pos(i)
              right = left + 1
  
              child = left
              if not left == self.n and not self._is_less(left, right):
                  child = right
  
              if not self._is_less(i, child):
                  self._exch(i, child)
                  i = child
              else:
                  break
  
      def _is_less(self, a, b):
          a_id = self.pq[a]
          b_id = self.pq[b]
          return self.keys[a_id] < self.keys[b_id]
  
      def _get_parent_pos(self, i):
          return i // 2
  
      def _get_left_child_pos(self, i):
          return i * 2
  
      def _exch(self, a, b):
          swap = self.pq[a]
          self.pq[a] = self.pq[b]
          self.pq[b] = swap
  
          if self.pq[a] is not None:
              self.qp[self.pq[a]] = a
          if self.pq[b] is not None:
              self.qp[self.pq[b]] = b
  
  
  class DijkstraShortestPath(object):
      def __init__(self, edge_weighted_digraph, source):
          self.digraph = edge_weighted_digraph
          self.source = source
  
          self.edge_to = [None for x in range(self.digraph.get_vertex_size())]
          self.dist_to = [
              float("infinity") for x in range(self.digraph.get_vertex_size())
          ]
          self.ipq = IndexMinPQ(self.digraph.get_vertex_size())
  
          self.dist_to[source] = 0.0
          self.ipq.insert(source, self.dist_to[source])
  
          while not self.ipq.is_empty():
              v = self.ipq.del_min()
              for edge in self.digraph.get_adj(v):
                  self._relax(edge)
  
      def _relax(self, edge):
          v = edge.edge_from()
          w = edge.edge_to()
          if self.dist_to[v] + edge.get_weight() < self.dist_to[w]:
              self.dist_to[w] = self.dist_to[v] + edge.get_weight()
              self.edge_to[w] = edge
  
              if self.ipq.contains(w):
                  self.ipq.decrease_key(w, self.dist_to[w])
              else:
                  self.ipq.insert(w, self.dist_to[w])
  
      def has_path_to(self, v):
          return self.dist_to[v] < float("infinity")
  
      def path_to(self, v):
          path = []
          while self.edge_to[v] is not None:
              edge = self.edge_to[v]
              path.append(edge)
              v = edge.edge_from()
          return path
  
  
  def solve():
      N, M = map(int, input().split())
      ABC = []
      for _ in range(M):
          ABC.append(tuple(map(int, input().split())))
  
      edges = []
      G = EdgeWeightedDigraph(N + 1)
      for a, b, c in ABC:
          edge_a = DirectedEdge(int(a), int(b), float(c), (a, b))
          edge_b = DirectedEdge(int(b), int(a), float(c), (a, b))
  
          G.add_edge(edge_a)
          G.add_edge(edge_b)
  
          edges.append((a, b))
  
      founds = set()
      for s in range(1, N + 1):
          sp = DijkstraShortestPath(G, s)
          for v in range(1, N + 1):
              if not v == s:
                  for e in sp.path_to(v):
                      # print(s, v, e)
                      founds.add(e.get_id())
  
      ans = len(edges) - len(founds)
  
      return ans
  
  
  if __name__ == "__main__":
      res = solve()
      print(res)
  
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."}]