import heapq

N, M = list(map(int, input().split()))

es = [[] for _ in range(N)]



INF = float("inf")

for i in range(M):

    a, b, c = list(map(int, input().split()))

    a, b = a-1, b-1

    es[a].append((b,c))

    es[b].append((a,c))





def djkstra(start, n, es):

    # start：スタート地点のノード

    # n：ノード数

    # es：edges, ある辺のコスト



    # 最初は全部未探索

    costs = [INF] * n

    costs[start] = 0

    checked = [False] * n #調べ終わったノードはTrue

    hq = [(0, start)] # スタートからスタートまでのコスト（＝０）とスタートの番号

    heapq.heapify(hq)

    while hq: # キューに残りがある限り

        cost, v = heapq.heappop(hq) # 取り出す

        if checked[v]:

            continue # 既に調べていたら飛ばす

        checked[v] = True

        costs[v] = cost

        for to, c in es[v]: # ノードvから伸びている辺すべてについて

            if costs[to] <= cost + c:

                continue # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす

            heapq.heappush(hq, (cost+c, to)) # toに行くまでの最短距離がcost+cに更新される

        

    return costs





min_cost = [[] for _ in range(N)]

for i in range(N):

    min_cost[i] = djkstra(i,N,es)



ans = 0

for i in range(len(es)):

    for to, c in es[i]:

        if min_cost[i][to] < c:

            #print("--------")

            #print(i,to,c)

            ans += 1



print((ans//2))

#print(min_cost)
import heapq



N,M = list(map(int, input().split()))

es = [[] for _ in range(N)]



for i in range(M):

    a,b,c = list(map(int, input().split()))

    es[a-1].append((c, b-1))

    es[b-1].append((c, a-1))



INF = float("inf")

# 全ノード間の最短距離を求める

d = [[INF for _ in range(N)] for _ in range(N)]



for i in range(N):

    q = []

    d[i][i] = 0

    heapq.heappush(q, (0, i))

    while q:

        cost, a = heapq.heappop(q)

        if d[i][a] < cost:

            continue

        for c,b in es[a]:

            if d[i][a] + c < d[i][b]:

                d[i][b] = d[i][a] + c

                heapq.heappush(q, (d[i][b], b))





# 全ての辺について、その辺の間の距離cがa->bまでの最短距離か確かめる

# ある辺がいずれかのノード間の最短経路に含まれるなら、その辺（が結ぶノード）も最短距離になるから。

cnt = 0

for i in range(N):

    for c, b in es[i]:

        if d[i][b] != c:

            cnt += 1



# 無向グラフなので２方向分カウントされてるから２で割る

print((cnt//2))
import heapq

N, M = list(map(int, input().split()))
es = [[] for _ in range(N)]
INF = float("inf")
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a - 1, b - 1
    es[a].append((b, c))
    es[b].append((a, c))


def djkstra(start, n, es):
    # start：スタート地点のノード
    # n：ノード数
    # es：edges, ある辺のコスト
    # 最初は全部未探索
    costs = [INF] * n
    costs[start] = 0
    checked = [False] * n  # 調べ終わったノードはTrue
    hq = [(0, start)]  # スタートからスタートまでのコスト（＝０）とスタートの番号
    heapq.heapify(hq)
    while hq:  # キューに残りがある限り
        cost, v = heapq.heappop(hq)  # 取り出す
        if checked[v]:
            continue  # 既に調べていたら飛ばす
        checked[v] = True
        costs[v] = cost
        for to, c in es[v]:  # ノードvから伸びている辺すべてについて
            if costs[to] <= cost + c:
                continue  # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす
            heapq.heappush(hq, (cost + c, to))  # toに行くまでの最短距離がcost+cに更新される
    return costs


min_cost = [[] for _ in range(N)]
for i in range(N):
    min_cost[i] = djkstra(i, N, es)
ans = 0
for i in range(len(es)):
    for to, c in es[i]:
        if min_cost[i][to] < c:
            # print("--------")
            # print(i,to,c)
            ans += 1
print((ans // 2))
# print(min_cost)

import heapq

N, M = list(map(int, input().split()))
es = [[] for _ in range(N)]
for i in range(M):
    a, b, c = list(map(int, input().split()))
    es[a - 1].append((c, b - 1))
    es[b - 1].append((c, a - 1))
INF = float("inf")
# 全ノード間の最短距離を求める
d = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    q = []
    d[i][i] = 0
    heapq.heappush(q, (0, i))
    while q:
        cost, a = heapq.heappop(q)
        if d[i][a] < cost:
            continue
        for c, b in es[a]:
            if d[i][a] + c < d[i][b]:
                d[i][b] = d[i][a] + c
                heapq.heappush(q, (d[i][b], b))
# 全ての辺について、その辺の間の距離cがa->bまでの最短距離か確かめる
# ある辺がいずれかのノード間の最短経路に含まれるなら、その辺（が結ぶノード）も最短距離になるから。
cnt = 0
for i in range(N):
    for c, b in es[i]:
        if d[i][b] != c:
            cnt += 1
# 無向グラフなので２方向分カウントされてるから２で割る
print((cnt // 2))

-INF = float("inf") -    a, b = a - 1, b - 1 -    es[a].append((b, c)) -    es[b].append((a, c)) - - -def djkstra(start, n, es): -    # start：スタート地点のノード -    # n：ノード数 -    # es：edges, ある辺のコスト -    # 最初は全部未探索 -    costs = [INF] * n -    costs[start] = 0 -    checked = [False] * n  # 調べ終わったノードはTrue -    hq = [(0, start)]  # スタートからスタートまでのコスト（＝０）とスタートの番号 -    heapq.heapify(hq) -    while hq:  # キューに残りがある限り -        cost, v = heapq.heappop(hq)  # 取り出す -        if checked[v]: -            continue  # 既に調べていたら飛ばす -        checked[v] = True -        costs[v] = cost -        for to, c in es[v]:  # ノードvから伸びている辺すべてについて -            if costs[to] <= cost + c: -                continue  # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす -            heapq.heappush(hq, (cost + c, to))  # toに行くまでの最短距離がcost+cに更新される -    return costs - - -min_cost = [[] for _ in range(N)] +    es[a - 1].append((c, b - 1)) +    es[b - 1].append((c, a - 1)) +INF = float("inf") +# 全ノード間の最短距離を求める +d = [[INF for _ in range(N)] for _ in range(N)] -    min_cost[i] = djkstra(i, N, es) -ans = 0 -for i in range(len(es)): -    for to, c in es[i]: -        if min_cost[i][to] < c: -            # print(i,to,c) -            ans += 1 -print((ans // 2)) -# print(min_cost) +    q = [] +    d[i][i] = 0 +    heapq.heappush(q, (0, i)) +    while q: +        cost, a = heapq.heappop(q) +        if d[i][a] < cost: +            continue +        for c, b in es[a]: +            if d[i][a] + c < d[i][b]: +                d[i][b] = d[i][a] + c +                heapq.heappush(q, (d[i][b], b)) +# 全ての辺について、その辺の間の距離cがa->bまでの最短距離か確かめる +# ある辺がいずれかのノード間の最短経路に含まれるなら、その辺（が結ぶノード）も最短距離になるから。 +cnt = 0 +for i in range(N): +    for c, b in es[i]: +        if d[i][b] != c: +            cnt += 1 +# 無向グラフなので２方向分カウントされてるから２で割る +print((cnt // 2))