#!/usr/bin/env python3



from heapq import heappush, heappop

import numpy as np



HUGE = 10 ** 15



def main():

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

    dist_mat = [[HUGE for j in range(n)] for i in range(n)]

    for i in range(m):

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

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

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

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

    res = 0

    for i in range(n):

        for j in range(i + 1, n):

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

                res += 1

    print(res)



def dijkstra(root, dist_mat):

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

    n = len(dist_mat)

    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 range(n):  # Use adjacent list for speedup

            if dist_mat[i][j] == HUGE:

                continue

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

                sp[j] = sp[i] + dist_mat[i][j]

                color[j] = 1

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

    return 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
from heapq import heappush, heappop
import numpy as np

HUGE = 10**15


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


def dijkstra(root, dist_mat):
    # rootからの距離のリストを返す (TLE本 p302)
    n = len(dist_mat)
    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 range(n):  # Use adjacent list for speedup
            if dist_mat[i][j] == HUGE:
                continue
            if color[j] != 2 and sp[i] + dist_mat[i][j] < sp[j]:
                sp[j] = sp[i] + dist_mat[i][j]
                color[j] = 1
                heappush(pq, (sp[j], j))
    return 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()

-import numpy as np -    dist_mat = [[HUGE for j in range(n)] for i in range(n)] +    dist_sets = [{} for i in range(n)] -        dist_mat[a1 - 1][b1 - 1] = c -        dist_mat[b1 - 1][a1 - 1] = c -    shortest_path_mat = [dijkstra(i, dist_mat) for i in range(n)] +        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)] -        for j in range(i + 1, n): -            if dist_mat[i][j] != HUGE and shortest_path_mat[i][j] < dist_mat[i][j]: +        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]: -def dijkstra(root, dist_mat): +def dijkstra(root, dist_sets): -    n = len(dist_mat) +    n = len(dist_sets) -        for j in range(n):  # Use adjacent list for speedup -            if dist_mat[i][j] == HUGE: -                continue -            if color[j] != 2 and sp[i] + dist_mat[i][j] < sp[j]: -                sp[j] = sp[i] + dist_mat[i][j] +        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]