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

INF = 10**6

Edge = [[INF]*N for _ in range(N)]

for _ in range(M):

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

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

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

    

dp = [[INF]*N for _ in range(N)]

for i in range(N):

    for j in range(N):

        if i == j:

            dp[i][j] = 0

        else:

            dp[i][j] = Edge[i][j]

    

for k in range(N):

    for i in range(N):

        for j in range(N):

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



ans = 0

for i in range(N-1):

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

        if Edge[i][j] == INF:

            continue

        if Edge[i][j] > dp[i][j]:

            ans += 1

            

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

inf = 10**8

d = [[inf]*N for _ in range(N)]

E = [[] for _ in range(N)]

for _ in range(M):

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

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

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

    E[a-1].append((b-1, c))



for i in range(N):

    d[i][i] = 0

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])



cnt = 0

for i in range(N):

    for e in E[i]:

        j = e[0]

        c = e[1]

        flag = False

        for k in range(N):

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

                if d[k][l] == d[k][i]+c+d[j][l] or d[k][l] == d[k][j]+c+d[i][l]:

                    cnt += 1

                    flag = True

                    break

            if flag:

                break

print((M-cnt))
N, M = list(map(int, input().split()))
INF = 10**6
Edge = [[INF] * N for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    Edge[a - 1][b - 1] = c
    Edge[b - 1][a - 1] = c
dp = [[INF] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            dp[i][j] = 0
        else:
            dp[i][j] = Edge[i][j]
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if Edge[i][j] == INF:
            continue
        if Edge[i][j] > dp[i][j]:
            ans += 1
print(ans)

N, M = list(map(int, input().split()))
inf = 10**8
d = [[inf] * N for _ in range(N)]
E = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = list(map(int, input().split()))
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c
    E[a - 1].append((b - 1, c))
for i in range(N):
    d[i][i] = 0
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])
cnt = 0
for i in range(N):
    for e in E[i]:
        j = e[0]
        c = e[1]
        flag = False
        for k in range(N):
            for l in range(k + 1, N):
                if d[k][l] == d[k][i] + c + d[j][l] or d[k][l] == d[k][j] + c + d[i][l]:
                    cnt += 1
                    flag = True
                    break
            if flag:
                break
print((M - cnt))

-INF = 10**6 -Edge = [[INF] * N for _ in range(N)] +inf = 10**8 +d = [[inf] * N for _ in range(N)] +E = [[] for _ in range(N)] -    Edge[a - 1][b - 1] = c -    Edge[b - 1][a - 1] = c -dp = [[INF] * N for _ in range(N)] +    d[a - 1][b - 1] = c +    d[b - 1][a - 1] = c +    E[a - 1].append((b - 1, c)) -    for j in range(N): -        if i == j: -            dp[i][j] = 0 -        else: -            dp[i][j] = Edge[i][j] +    d[i][i] = 0 -            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) -ans = 0 -for i in range(N - 1): -    for j in range(i + 1, N): -        if Edge[i][j] == INF: -            continue -        if Edge[i][j] > dp[i][j]: -            ans += 1 -print(ans) +            d[i][j] = min(d[i][j], d[i][k] + d[k][j]) +cnt = 0 +for i in range(N): +    for e in E[i]: +        j = e[0] +        c = e[1] +        flag = False +        for k in range(N): +            for l in range(k + 1, N): +                if d[k][l] == d[k][i] + c + d[j][l] or d[k][l] == d[k][j] + c + d[i][l]: +                    cnt += 1 +                    flag = True +                    break +            if flag: +                break +print((M - cnt))