import heapq

INFTY = 10**6

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

G = {i:[] for i in range(1,N+1)}

Arc = {}

for _ in range(M):

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

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

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

    Arc[(a,b)]=0

    Arc[(b,a)]=0

for s in range(1,N+1):

    dist = [INFTY for _ in range(N+1)]

    dist[s] = 0

    hist = [0 for _ in range(N+1)]

    heap = [(0,s)]

    pre = {}

    while heap:

        d,x = heapq.heappop(heap)

        if dist[x]<d:continue

        hist[x] = 1

        for y,e in G[x]:

            if hist[y]==0 and dist[y]>d+e:

                dist[y] = d+e

                pre[y] = x

                heapq.heappush(heap,(d+e,y))

    for j in pre:

        a = j

        while pre[a]!=s:

            b = pre[a]

            Arc[(a,b)] = 1

            Arc[(b,a)] = 1

            a = b

        Arc[(a,s)] = 1

        Arc[(s,a)] = 1

cnt = 0

for x in Arc:

    if Arc[x]==0:

        cnt += 1

print((cnt//2))
INFTY = 10**5+10

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

L = [list(map(int,input().split())) for _ in range(M)]

G = {i:[] for i in range(1,N+1)}

dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]

for j in range(M):

    a,b,c = L[j]

    G[a].append(b)

    G[b].append(a)

    dist[a][b] = c

    dist[b][a] = c

for k in range(1,N+1):

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

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

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

cnt = 0

for j in range(M):

    a,b,c = L[j]

    if dist[a][b]<c:

        cnt += 1

print(cnt)
import heapq

INFTY = 10**6
N, M = list(map(int, input().split()))
G = {i: [] for i in range(1, N + 1)}
Arc = {}
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    G[a].append((b, c))
    G[b].append((a, c))
    Arc[(a, b)] = 0
    Arc[(b, a)] = 0
for s in range(1, N + 1):
    dist = [INFTY for _ in range(N + 1)]
    dist[s] = 0
    hist = [0 for _ in range(N + 1)]
    heap = [(0, s)]
    pre = {}
    while heap:
        d, x = heapq.heappop(heap)
        if dist[x] < d:
            continue
        hist[x] = 1
        for y, e in G[x]:
            if hist[y] == 0 and dist[y] > d + e:
                dist[y] = d + e
                pre[y] = x
                heapq.heappush(heap, (d + e, y))
    for j in pre:
        a = j
        while pre[a] != s:
            b = pre[a]
            Arc[(a, b)] = 1
            Arc[(b, a)] = 1
            a = b
        Arc[(a, s)] = 1
        Arc[(s, a)] = 1
cnt = 0
for x in Arc:
    if Arc[x] == 0:
        cnt += 1
print((cnt // 2))

INFTY = 10**5 + 10
N, M = list(map(int, input().split()))
L = [list(map(int, input().split())) for _ in range(M)]
G = {i: [] for i in range(1, N + 1)}
dist = [[INFTY for _ in range(N + 1)] for _ in range(N + 1)]
for j in range(M):
    a, b, c = L[j]
    G[a].append(b)
    G[b].append(a)
    dist[a][b] = c
    dist[b][a] = c
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
cnt = 0
for j in range(M):
    a, b, c = L[j]
    if dist[a][b] < c:
        cnt += 1
print(cnt)

-import heapq - -INFTY = 10**6 +INFTY = 10**5 + 10 +L = [list(map(int, input().split())) for _ in range(M)] -Arc = {} -for _ in range(M): -    a, b, c = list(map(int, input().split())) -    G[a].append((b, c)) -    G[b].append((a, c)) -    Arc[(a, b)] = 0 -    Arc[(b, a)] = 0 -for s in range(1, N + 1): -    dist = [INFTY for _ in range(N + 1)] -    dist[s] = 0 -    hist = [0 for _ in range(N + 1)] -    heap = [(0, s)] -    pre = {} -    while heap: -        d, x = heapq.heappop(heap) -        if dist[x] < d: -            continue -        hist[x] = 1 -        for y, e in G[x]: -            if hist[y] == 0 and dist[y] > d + e: -                dist[y] = d + e -                pre[y] = x -                heapq.heappush(heap, (d + e, y)) -    for j in pre: -        a = j -        while pre[a] != s: -            b = pre[a] -            Arc[(a, b)] = 1 -            Arc[(b, a)] = 1 -            a = b -        Arc[(a, s)] = 1 -        Arc[(s, a)] = 1 +dist = [[INFTY for _ in range(N + 1)] for _ in range(N + 1)] +for j in range(M): +    a, b, c = L[j] +    G[a].append(b) +    G[b].append(a) +    dist[a][b] = c +    dist[b][a] = c +for k in range(1, N + 1): +    for i in range(1, N + 1): +        for j in range(1, N + 1): +            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) -for x in Arc: -    if Arc[x] == 0: +for j in range(M): +    a, b, c = L[j] +    if dist[a][b] < c: -print((cnt // 2)) +print(cnt)