import heapq

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

R=[]

G=[[] for i in range(N)]

for i in range(M):

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

    a,b=a-1,b-1

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

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

    R.append((a,b,c))

Q=[[0]*N for i in range(N)]

INF=10**9

for i in range(N):

    stack=[]

    g=[INF for i in range(N)]

    g[i]=0

    n=1

    for b,c in G[i]:

        heapq.heappush(stack,(g[i]+c,i,b))

    used=[[0]*N for i in range(N)]

    while(stack):

        if n==N:

            break

        c,a,b=heapq.heappop(stack)

        g[b]=min(g[b],c)

        used[a][b]=1

        used[b][a]=1

        for j in G[b]:

            if used[b][j[0]] or g[j[0]]!=INF:

                continue

            heapq.heappush(stack,(g[b]+j[1],b,j[0]))

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

        Q[i][j]=g[j]

ans=0

for a,b,c in R:

    if b<a:

        a,b=b,a

    if Q[a][b]<c:

        ans+=1

print(ans)

import heapq

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

R=[]

G=[[] for i in range(N)]

for i in range(M):

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

    a,b=a-1,b-1

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

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

    R.append((a,b,c))

Q=[[0]*N for i in range(N)]

INF=10**9

for i in range(N):

    stack=[]

    g=[INF for i in range(N)]

    g[i]=0

    n=1

    for b,c in G[i]:

        heapq.heappush(stack,(g[i]+c,i,b))

    used=[[0]*N for i in range(N)]

    while(stack):

        if n==N:

            break

        c,a,b=heapq.heappop(stack)

        g[b]=min(g[b],c)



        used[a][b]=1

        used[b][a]=1

        for j in G[b]:

            if used[b][j[0]] or g[j[0]]!=INF:

                continue

            if g[j[0]]<=g[b]+j[1]:

                continue

            heapq.heappush(stack,(g[b]+j[1],b,j[0]))

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

        Q[i][j]=g[j]

ans=0

for a,b,c in R:

    if b<a:

        a,b=b,a

    if Q[a][b]<c:

        ans+=1

print(ans)

import heapq

N, M = list(map(int, input().split()))
R = []
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))
    R.append((a, b, c))
Q = [[0] * N for i in range(N)]
INF = 10**9
for i in range(N):
    stack = []
    g = [INF for i in range(N)]
    g[i] = 0
    n = 1
    for b, c in G[i]:
        heapq.heappush(stack, (g[i] + c, i, b))
    used = [[0] * N for i in range(N)]
    while stack:
        if n == N:
            break
        c, a, b = heapq.heappop(stack)
        g[b] = min(g[b], c)
        used[a][b] = 1
        used[b][a] = 1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]] != INF:
                continue
            heapq.heappush(stack, (g[b] + j[1], b, j[0]))
    for j in range(i + 1, N):
        Q[i][j] = g[j]
ans = 0
for a, b, c in R:
    if b < a:
        a, b = b, a
    if Q[a][b] < c:
        ans += 1
print(ans)

import heapq

N, M = list(map(int, input().split()))
R = []
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))
    R.append((a, b, c))
Q = [[0] * N for i in range(N)]
INF = 10**9
for i in range(N):
    stack = []
    g = [INF for i in range(N)]
    g[i] = 0
    n = 1
    for b, c in G[i]:
        heapq.heappush(stack, (g[i] + c, i, b))
    used = [[0] * N for i in range(N)]
    while stack:
        if n == N:
            break
        c, a, b = heapq.heappop(stack)
        g[b] = min(g[b], c)
        used[a][b] = 1
        used[b][a] = 1
        for j in G[b]:
            if used[b][j[0]] or g[j[0]] != INF:
                continue
            if g[j[0]] <= g[b] + j[1]:
                continue
            heapq.heappush(stack, (g[b] + j[1], b, j[0]))
    for j in range(i + 1, N):
        Q[i][j] = g[j]
ans = 0
for a, b, c in R:
    if b < a:
        a, b = b, a
    if Q[a][b] < c:
        ans += 1
print(ans)

+            if g[j[0]] <= g[b] + j[1]: +                continue