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 Graph:
      # 初期変数は頂点数、辺数、標準入力から受け取った配列形式の入力
      def __init__(self, vertex_num, node_num, naive_input):
          self.vertex_num = vertex_num
          self.node_num = node_num
          # nodeには入力時のインデックスも含む
          # [接続ノード , インッデクス]のarray
          node = [[] for _ in range(vertex_num)]
          for i in range(node_num):
              u, v = naive_input[i][:2]
              w = naive_input[i][2]
              node[u].append([v, i, w])
              node[v].append([u, i, w])
          self.node = node
          # それぞれの頂点の辺の数
          self.node_num_arr = list(map(lambda x: len(x), node))
  
      # 頂点nowから順にbfs
      def bfs(self, s=0):
          # 最短経路＋αで問題を解くと思うのでcal_distance内で問題を解くための関数を実行する形の方が自然？
          def cal_distance(
              now_edge, next_edge_info, distance_arr, before_vertex_arr, queue, l_ind
          ):
              next_edge = next_edge_info[0]
              weight = next_edge_info[2]
              cal_distance_val = distance_arr[now_edge] + weight
              if before_vertex_arr[next_edge] == -1:
                  queue[l_ind] = next_edge
                  # print("queue is updated")
                  l_ind += 1
              if cal_distance_val < distance_arr[next_edge]:
                  # 配列渡しなのでこのあたりは返り値に持たせる必要無し
                  distance_arr[next_edge] = cal_distance_val
                  before_vertex_arr[next_edge] = now_edge
                  # for debug
                  # print(now_edge,"→",next_edge,":",cal_distance_val)
                  # print(distance_arr)
                  # print(before_vertex)
  
              return l_ind
  
          # bfs用のキュー
          q = [-1 for _ in range(self.vertex_num)]
          # pypyを使うときは要変更
          # ダイクストラ使用に伴って削除
          # 訪問済み頂点は距離から導出
          # cal_node_num_arr=self.node_num_arr.copy()
          now_ind = 0
          q[now_ind] = s
          last_ind = 1
  
          distance = [float("inf") for _ in range(self.vertex_num)]
          distance[s] = 0
          before_vertex = [-1 for _ in range(self.vertex_num)]
          before_vertex[s] = s
          index_arr = [-1 for _ in range(self.node_num)]
  
          while last_ind < self.vertex_num:
              now_edge = q[now_ind]
              """
              print()
              print()
              print("now_node:",now_edge)
              print("now_ind:",now_ind,"last_ind",last_ind)
              print(q)
              print(before_vertex)
              """
              for next_edge_info in self.node[now_edge]:
                  # インデックスを利用したいときは要修正
                  # cal_node_num_arr[now_edge]-=1
                  # cal_node_num_arr[next_edge]-=1
                  # q[last_ind]=next_edge
                  ##ここにやりたい処理をぶち込む！！
                  #######cal_hogehoge()
  
                  # 頂点sから各頂点までの距離を計算する
  
                  last_ind = cal_distance(
                      now_edge, next_edge_info, distance, before_vertex, q, last_ind
                  )
  
              now_ind += 1
  
          return distance
  
  
  n, m = list(map(int, input().split()))
  """
  maze=[[i for i in input()] for _ in range(n)]
  graph=[[] for _ in range(n*m)]
  q_num=0
  for i in range(n):
      for j in range(m):
          if maze[i][j]=="#":
              continue
          ind=i*m+j
          q_num+=1
          #move[i][j]=ind
          if i!=0:
              if maze[i-1][j]!="#":
                  graph[ind].append((i-1)*m+j)
          if i!=n-1:
              if maze[i+1][j]!="#":
                  graph[ind].append((i+1)*m+j)
          if j!=0:
              if maze[i][j-1]!="#":
                  graph[ind].append(i*m+j-1)
   
          if j!=m-1:
              if maze[i][j+1]!="#":
                  graph[ind].append(i*m+j+1)
  
  a=[]
  for num,i in enumerate(graph):
      for j in i:
          a.append([num,j,1])
  #print(a)
  tmp=0
  for i in maze:
      for j in i:
          if j==".":
              tmp+=1
  n=tmp
  m=len(a)
  """
  a = [list(map(int, input().split())) for _ in range(m)]
  a = list(map(lambda x: [x[0] - 1, x[1] - 1, x[2]], a))
  G = Graph(n, m, a)
  ans = 0
  for i in range(n):
      cal = G.bfs(i)
  
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."}]