def main():
    from collections import deque
    from itertools import combinations
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for idx in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        g[a].add((b, c, idx))  # to,weight,idx
        g[b].add((a, c, idx))  # to,weight,idx

    used_edge = 0

    dq = deque()
    for frm, to in combinations(range(N), r=2):
        dq.append((frm, 0))

        dist = [1000 * 100 + 10] * N
        dist[frm] = 0
        while dq:
            v, c = dq.popleft()
            if dist[v] < c: continue
            for u, dc, idx in g[v]:
                nc = c + dc
                if dist[u] > nc:
                    dist[u] = nc
                    dq.append((u, nc))

        dq.append((to, 0))
        while dq:
            v, b = dq.popleft()
            if v == frm:
                used_edge |= b
                continue

            for u, dc, idx in g[v]:
                if dist[u] == dist[v] - dc:
                    dq.append((u, b | 1 << idx))

    print(M - bin(used_edge).count('1'))


if __name__ == '__main__':
    main()
