import queue



INF = 123456789



def main():

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



    G = [[] for _ in range(n)]

    for _ in range(m):

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

        a -= 1

        b -= 1

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

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



    used = set()

    for i in range(n):

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

        par = [-1 for _ in range(n)]



        # dijkstra

        que = queue.PriorityQueue()

        d[i] = 0

        que.put((0,i))

        while not que.empty():

            p = que.get()

            v = p[1]

            if d[v] < p[0]:

                continue

            for (to,cost) in G[v]:

                if d[to] > d[v]+cost:

                    d[to] = d[v]+cost

                    par[to] = v

                    que.put((d[to],to))



        for j in range(n):

            if i != j:

                a,b = j,par[j]

                if a>b:

                    a,b = b,a

                used.add((a,b))



    print((m - len(used)))



if __name__ == '__main__':

    main()

INF = 123456789



def main():

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



    d = [ [INF for i in range(n)] for j in range(n) ]

    for i in range(n):

        d[i][i] = 0



    a = [0 for _ in range(m)]

    b = [0 for _ in range(m)]

    c = [0 for _ in range(m)]

    for i in range(m):

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

        a[i] -= 1

        b[i] -= 1

        d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i])

        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i])



    # Warshall-Floyd

    for k in range(n):

        for i in range(n):

            for j in range(n):

                d[i][j] = min(d[i][j], d[i][k]+d[k][j])



    ans = 0

    for i in range(m):

        found = 1

        for j in range(n):

            if d[j][a[i]] + c[i] == d[j][b[i]]:

                found = 0

                break

        ans += found

    print(ans)



if __name__ == '__main__':

    main()

import queue

INF = 123456789


def main():
    n, m = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = list(map(int, input().split()))
        a -= 1
        b -= 1
        G[a].append((b, c))
        G[b].append((a, c))
    used = set()
    for i in range(n):
        d = [INF for _ in range(n)]
        par = [-1 for _ in range(n)]
        # dijkstra
        que = queue.PriorityQueue()
        d[i] = 0
        que.put((0, i))
        while not que.empty():
            p = que.get()
            v = p[1]
            if d[v] < p[0]:
                continue
            for (to, cost) in G[v]:
                if d[to] > d[v] + cost:
                    d[to] = d[v] + cost
                    par[to] = v
                    que.put((d[to], to))
        for j in range(n):
            if i != j:
                a, b = j, par[j]
                if a > b:
                    a, b = b, a
                used.add((a, b))
    print((m - len(used)))


if __name__ == "__main__":
    main()

INF = 123456789


def main():
    n, m = list(map(int, input().split()))
    d = [[INF for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 0
    a = [0 for _ in range(m)]
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]
    for i in range(m):
        a[i], b[i], c[i] = list(map(int, input().split()))
        a[i] -= 1
        b[i] -= 1
        d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i])
        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i])
    # Warshall-Floyd
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    ans = 0
    for i in range(m):
        found = 1
        for j in range(n):
            if d[j][a[i]] + c[i] == d[j][b[i]]:
                found = 0
                break
        ans += found
    print(ans)


if __name__ == "__main__":
    main()

-import queue - -    G = [[] for _ in range(n)] -    for _ in range(m): -        a, b, c = list(map(int, input().split())) -        a -= 1 -        b -= 1 -        G[a].append((b, c)) -        G[b].append((a, c)) -    used = set() +    d = [[INF for i in range(n)] for j in range(n)] -        d = [INF for _ in range(n)] -        par = [-1 for _ in range(n)] -        # dijkstra -        que = queue.PriorityQueue() -        d[i] = 0 -        que.put((0, i)) -        while not que.empty(): -            p = que.get() -            v = p[1] -            if d[v] < p[0]: -                continue -            for (to, cost) in G[v]: -                if d[to] > d[v] + cost: -                    d[to] = d[v] + cost -                    par[to] = v -                    que.put((d[to], to)) +        d[i][i] = 0 +    a = [0 for _ in range(m)] +    b = [0 for _ in range(m)] +    c = [0 for _ in range(m)] +    for i in range(m): +        a[i], b[i], c[i] = list(map(int, input().split())) +        a[i] -= 1 +        b[i] -= 1 +        d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]) +        d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i]) +    # Warshall-Floyd +    for k in range(n): +        for i in range(n): +            for j in range(n): +                d[i][j] = min(d[i][j], d[i][k] + d[k][j]) +    ans = 0 +    for i in range(m): +        found = 1 -            if i != j: -                a, b = j, par[j] -                if a > b: -                    a, b = b, a -                used.add((a, b)) -    print((m - len(used))) +            if d[j][a[i]] + c[i] == d[j][b[i]]: +                found = 0 +                break +        ans += found +    print(ans)