

# D - Candidates of No Shortest Paths



MAXI = 999999999



# 入力

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

cost = [[-1 for i in range(N)] for j in range(N)]



for i in range(M):

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

    cost[a - 1][b - 1] = c

    cost[b - 1][a - 1] = c



# iからjへの最短距離を表すテーブルの初期化

dist = [[MAXI for i in range(N)] for j in range(N)]



# iからjへの辺があったら、最短距離をその辺のコストで初期化

for i in range(N):

    for j in range(N):

        if i == j:

            dist[i][j] = 0

        elif cost[i][j] != -1:

            dist[i][j] = cost[i][j]

            dist[j][i] = dist[i][j]



# ワーシャルフロイドで各i,j間の最短距離を求めておく

for k in range(N):

    for i in range(N):

        for j in range(N):

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



ans = 0



for i in range(N):

    for j in range(i, N):

        # i,j間に辺があって、そこを通らない方が近道になるとき、全ての最短経路でその辺は使われない

        if cost[i][j] != -1 and cost[i][j] != dist[i][j]:

            ans += 1



print(ans)
import sys



inf = 1<<60



def solve():

    N, M = list(map(int, sys.stdin.readline().split()))



    cost = [[inf]*N for i in range(N)]



    for mi in range(M):

        a, b, c = list(map(int, sys.stdin.readline().split()))

        a, b = a-1, b-1

        cost[a][b] = cost[b][a] = c



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



    for i in range(N):

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

            dist[i][j] = dist[j][i] = cost[i][j]



    for k in range(N):

        for i in range(N):

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

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



    ans = 0



    for i in range(N):

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

            if cost[i][j] < inf and cost[i][j] != dist[i][j]:

                ans += 1



    print(ans)



if __name__ == '__main__':

    solve()
# D - Candidates of No Shortest Paths
MAXI = 999999999
# 入力
N, M = list(map(int, input().split()))
cost = [[-1 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b, c = list(map(int, input().split()))
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c
# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]
# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]
# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ans = 0
for i in range(N):
    for j in range(i, N):
        # i,j間に辺があって、そこを通らない方が近道になるとき、全ての最短経路でその辺は使われない
        if cost[i][j] != -1 and cost[i][j] != dist[i][j]:
            ans += 1
print(ans)

import sys

inf = 1 << 60


def solve():
    N, M = list(map(int, sys.stdin.readline().split()))
    cost = [[inf] * N for i in range(N)]
    for mi in range(M):
        a, b, c = list(map(int, sys.stdin.readline().split()))
        a, b = a - 1, b - 1
        cost[a][b] = cost[b][a] = c
    dist = [[0] * N for i in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            dist[i][j] = dist[j][i] = cost[i][j]
    for k in range(N):
        for i in range(N):
            for j in range(i + 1, N):
                dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if cost[i][j] < inf and cost[i][j] != dist[i][j]:
                ans += 1
    print(ans)


if __name__ == "__main__":
    solve()

-# D - Candidates of No Shortest Paths -MAXI = 999999999 -# 入力 -N, M = list(map(int, input().split())) -cost = [[-1 for i in range(N)] for j in range(N)] -for i in range(M): -    a, b, c = list(map(int, input().split())) -    cost[a - 1][b - 1] = c -    cost[b - 1][a - 1] = c -# iからjへの最短距離を表すテーブルの初期化 -dist = [[MAXI for i in range(N)] for j in range(N)] -# iからjへの辺があったら、最短距離をその辺のコストで初期化 -for i in range(N): -    for j in range(N): -        if i == j: -            dist[i][j] = 0 -        elif cost[i][j] != -1: -            dist[i][j] = cost[i][j] -            dist[j][i] = dist[i][j] -# ワーシャルフロイドで各i,j間の最短距離を求めておく -for k in range(N): +import sys + +inf = 1 << 60 + + +def solve(): +    N, M = list(map(int, sys.stdin.readline().split())) +    cost = [[inf] * N for i in range(N)] +    for mi in range(M): +        a, b, c = list(map(int, sys.stdin.readline().split())) +        a, b = a - 1, b - 1 +        cost[a][b] = cost[b][a] = c +    dist = [[0] * N for i in range(N)] -        for j in range(N): -            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) -ans = 0 -for i in range(N): -    for j in range(i, N): -        # i,j間に辺があって、そこを通らない方が近道になるとき、全ての最短経路でその辺は使われない -        if cost[i][j] != -1 and cost[i][j] != dist[i][j]: -            ans += 1 -print(ans) +        for j in range(i + 1, N): +            dist[i][j] = dist[j][i] = cost[i][j] +    for k in range(N): +        for i in range(N): +            for j in range(i + 1, N): +                dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) +    ans = 0 +    for i in range(N): +        for j in range(i + 1, N): +            if cost[i][j] < inf and cost[i][j] != dist[i][j]: +                ans += 1 +    print(ans) + + +if __name__ == "__main__": +    solve()