#!/usr/bin/env python3



from heapq import heappush, heappop



HUGE = 10 ** 15



def main():

    n, m = list(map(int, input().split()))

    dist_sets = [{} for i in range(n)]

    for i in range(m):

        a1, b1, c = list(map(int, input().split()))

        dist_sets[a1 - 1][b1 - 1] = c

        dist_sets[b1 - 1][a1 - 1] = c

    shortest_path_mat = [dijkstra(i, dist_sets) for i in range(n)]

    res = 0

    for i in range(n):

        for j in list(dist_sets[i].keys()):

            if i > j:

                continue

            if dist_sets[i][j] != HUGE and shortest_path_mat[i][j] < dist_sets[i][j]:

                res += 1

    print(res)



def dijkstra(root, dist_sets):

    # rootからの距離のリストを返す (TLE本 p302)

    n = len(dist_sets)

    sp = [(0 if i == root else HUGE) for i in range(n)]  # Shortest path from root

    color = [(2 if i == root else 0) for i in range(n)]  # 0: unknown. 1: one path is found. 2: shortest path is found

    pq = []

    heappush(pq, (sp[root], root))

    while len(pq) > 0:

        sp_i_when_queued, i = heappop(pq)

        color[i] = 2

        if sp[i] < sp_i_when_queued:

            continue

        for j in list(dist_sets[i].keys()):

            if color[j] != 2 and sp[i] + dist_sets[i][j] < sp[j]:

                sp[j] = sp[i] + dist_sets[i][j]

                color[j] = 1

                heappush(pq, (sp[j], j))

    return sp



main()

#!/usr/bin/env python3

# 本スクリプトを通じて以下の意味で用いる

# dist: 直接結ぶエッジの長さ

# shortest path (sp): 他のノードを経由しうる最短経路



from heapq import heappush, heappop



HUGE = 10 ** 15



def main():

    n, m = list(map(int, input().split()))

    dist_sets = [{} for i in range(n)]

    for i in range(m):

        a1, b1, c = list(map(int, input().split()))

        dist_sets[a1 - 1][b1 - 1] = c

        dist_sets[b1 - 1][a1 - 1] = c

    shortest_path_mat = [get_shortest_path_dijkstra(i, dist_sets) for i in range(n)]

    res = 0

    for i in range(n):

        for j in list(dist_sets[i].keys()):

            if i > j:

                continue

            if shortest_path_mat[i][j] < dist_sets[i][j]:

                res += 1

    print(res)



def get_shortest_path_dijkstra(root, dist_sets):

    n = len(dist_sets)

    known_sp = [HUGE for i in range(n)]

    known_sp[root] = 0

    determined = [(i == root) for i in range(n)]

    pq = [(known_sp[root], root)]  # 第一要素はキュー追加時の shortest path 候補

    while len(pq) > 0:

        sp_cand, i = heappop(pq)

        determined[i] = True

        if known_sp[i] < sp_cand:

            continue

        for j, dist_ij in list(dist_sets[i].items()):

            if determined[j]:

                continue

            if known_sp[i] + dist_ij < known_sp[j]:

                known_sp[j] = known_sp[i] + dist_ij

                heappush(pq, (known_sp[j], j))

    return known_sp



main()

#!/usr/bin/env python3
from heapq import heappush, heappop

HUGE = 10**15


def main():
    n, m = list(map(int, input().split()))
    dist_sets = [{} for i in range(n)]
    for i in range(m):
        a1, b1, c = list(map(int, input().split()))
        dist_sets[a1 - 1][b1 - 1] = c
        dist_sets[b1 - 1][a1 - 1] = c
    shortest_path_mat = [dijkstra(i, dist_sets) for i in range(n)]
    res = 0
    for i in range(n):
        for j in list(dist_sets[i].keys()):
            if i > j:
                continue
            if dist_sets[i][j] != HUGE and shortest_path_mat[i][j] < dist_sets[i][j]:
                res += 1
    print(res)


def dijkstra(root, dist_sets):
    # rootからの距離のリストを返す (TLE本 p302)
    n = len(dist_sets)
    sp = [(0 if i == root else HUGE) for i in range(n)]  # Shortest path from root
    color = [
        (2 if i == root else 0) for i in range(n)
    ]  # 0: unknown. 1: one path is found. 2: shortest path is found
    pq = []
    heappush(pq, (sp[root], root))
    while len(pq) > 0:
        sp_i_when_queued, i = heappop(pq)
        color[i] = 2
        if sp[i] < sp_i_when_queued:
            continue
        for j in list(dist_sets[i].keys()):
            if color[j] != 2 and sp[i] + dist_sets[i][j] < sp[j]:
                sp[j] = sp[i] + dist_sets[i][j]
                color[j] = 1
                heappush(pq, (sp[j], j))
    return sp


main()

#!/usr/bin/env python3
# 本スクリプトを通じて以下の意味で用いる
# dist: 直接結ぶエッジの長さ
# shortest path (sp): 他のノードを経由しうる最短経路
from heapq import heappush, heappop

HUGE = 10**15


def main():
    n, m = list(map(int, input().split()))
    dist_sets = [{} for i in range(n)]
    for i in range(m):
        a1, b1, c = list(map(int, input().split()))
        dist_sets[a1 - 1][b1 - 1] = c
        dist_sets[b1 - 1][a1 - 1] = c
    shortest_path_mat = [get_shortest_path_dijkstra(i, dist_sets) for i in range(n)]
    res = 0
    for i in range(n):
        for j in list(dist_sets[i].keys()):
            if i > j:
                continue
            if shortest_path_mat[i][j] < dist_sets[i][j]:
                res += 1
    print(res)


def get_shortest_path_dijkstra(root, dist_sets):
    n = len(dist_sets)
    known_sp = [HUGE for i in range(n)]
    known_sp[root] = 0
    determined = [(i == root) for i in range(n)]
    pq = [(known_sp[root], root)]  # 第一要素はキュー追加時の shortest path 候補
    while len(pq) > 0:
        sp_cand, i = heappop(pq)
        determined[i] = True
        if known_sp[i] < sp_cand:
            continue
        for j, dist_ij in list(dist_sets[i].items()):
            if determined[j]:
                continue
            if known_sp[i] + dist_ij < known_sp[j]:
                known_sp[j] = known_sp[i] + dist_ij
                heappush(pq, (known_sp[j], j))
    return known_sp


main()

+# 本スクリプトを通じて以下の意味で用いる +# dist: 直接結ぶエッジの長さ +# shortest path (sp): 他のノードを経由しうる最短経路 -    shortest_path_mat = [dijkstra(i, dist_sets) for i in range(n)] +    shortest_path_mat = [get_shortest_path_dijkstra(i, dist_sets) for i in range(n)] -            if dist_sets[i][j] != HUGE and shortest_path_mat[i][j] < dist_sets[i][j]: +            if shortest_path_mat[i][j] < dist_sets[i][j]: -def dijkstra(root, dist_sets): -    # rootからの距離のリストを返す (TLE本 p302) +def get_shortest_path_dijkstra(root, dist_sets): -    sp = [(0 if i == root else HUGE) for i in range(n)]  # Shortest path from root -    color = [ -        (2 if i == root else 0) for i in range(n) -    ]  # 0: unknown. 1: one path is found. 2: shortest path is found -    pq = [] -    heappush(pq, (sp[root], root)) +    known_sp = [HUGE for i in range(n)] +    known_sp[root] = 0 +    determined = [(i == root) for i in range(n)] +    pq = [(known_sp[root], root)]  # 第一要素はキュー追加時の shortest path 候補 -        sp_i_when_queued, i = heappop(pq) -        color[i] = 2 -        if sp[i] < sp_i_when_queued: +        sp_cand, i = heappop(pq) +        determined[i] = True +        if known_sp[i] < sp_cand: -        for j in list(dist_sets[i].keys()): -            if color[j] != 2 and sp[i] + dist_sets[i][j] < sp[j]: -                sp[j] = sp[i] + dist_sets[i][j] -                color[j] = 1 -                heappush(pq, (sp[j], j)) -    return sp +        for j, dist_ij in list(dist_sets[i].items()): +            if determined[j]: +                continue +            if known_sp[i] + dist_ij < known_sp[j]: +                known_sp[j] = known_sp[i] + dist_ij +                heappush(pq, (known_sp[j], j)) +    return known_sp