INF = 10**18



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

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

graph = [[INF for j in range(N)] for i in range(N)]



for i in range(N):

    graph[i][i] = 0



for e in edge:

    graph[e[0]-1][e[1]-1] = e[2]

    graph[e[1]-1][e[0]-1] = e[2]

    

for k in range(N):

    for i in range(N):

        for j in range(N):

            if graph[i][k] != INF and graph[k][j] != INF:

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



ans = 0



for e in edge:

    if graph[e[0]-1][e[1]-1] != e[2]:

        ans += 1

        

print(ans)
class Graph():  #non-directed

    def __init__(self, n, edge, indexed=1):

        self.n = n

        self.edge = edge

        self.indexed = indexed

        self.graph = [[] for _ in range(n)]

        for e in edge:

            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))

            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))



    def warshall_floyd(self, INF=10**18):

        dist = [[INF for j in range(self.n)] for i in range(self.n)]

        for i in range(self.n):

            dist[i][i] = 0

        for i in range(self.n):

            for j, cost in self.graph[i]:

                dist[i][j] = cost

        for k in range(self.n):

            for i in range(self.n):

                for j in range(self.n):

                    if dist[i][k] != INF and dist[k][j] != INF:

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

        return dist





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

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



g = Graph(N, E)

wf = g.warshall_floyd()



res = 0



for i in range(M):

    a, b, c = E[i]

    if wf[a - 1][b - 1] != c:

        res += 1



print(res)
INF = 10**18
N, M = list(map(int, input().split()))
edge = [list(map(int, input().split())) for _ in range(M)]
graph = [[INF for j in range(N)] for i in range(N)]
for i in range(N):
    graph[i][i] = 0
for e in edge:
    graph[e[0] - 1][e[1] - 1] = e[2]
    graph[e[1] - 1][e[0] - 1] = e[2]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][k] != INF and graph[k][j] != INF:
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for e in edge:
    if graph[e[0] - 1][e[1] - 1] != e[2]:
        ans += 1
print(ans)

class Graph:  # non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


N, M = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(M)]
g = Graph(N, E)
wf = g.warshall_floyd()
res = 0
for i in range(M):
    a, b, c = E[i]
    if wf[a - 1][b - 1] != c:
        res += 1
print(res)

-INF = 10**18 +class Graph:  # non-directed +    def __init__(self, n, edge, indexed=1): +        self.n = n +        self.edge = edge +        self.indexed = indexed +        self.graph = [[] for _ in range(n)] +        for e in edge: +            self.graph[e[0] - indexed].append((e[1] - indexed, e[2])) +            self.graph[e[1] - indexed].append((e[0] - indexed, e[2])) + +    def warshall_floyd(self, INF=10**18): +        dist = [[INF for j in range(self.n)] for i in range(self.n)] +        for i in range(self.n): +            dist[i][i] = 0 +        for i in range(self.n): +            for j, cost in self.graph[i]: +                dist[i][j] = cost +        for k in range(self.n): +            for i in range(self.n): +                for j in range(self.n): +                    if dist[i][k] != INF and dist[k][j] != INF: +                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) +        return dist + + -edge = [list(map(int, input().split())) for _ in range(M)] -graph = [[INF for j in range(N)] for i in range(N)] -for i in range(N): -    graph[i][i] = 0 -for e in edge: -    graph[e[0] - 1][e[1] - 1] = e[2] -    graph[e[1] - 1][e[0] - 1] = e[2] -for k in range(N): -    for i in range(N): -        for j in range(N): -            if graph[i][k] != INF and graph[k][j] != INF: -                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) -ans = 0 -for e in edge: -    if graph[e[0] - 1][e[1] - 1] != e[2]: -        ans += 1 -print(ans) +E = [tuple(map(int, input().split())) for _ in range(M)] +g = Graph(N, E) +wf = g.warshall_floyd() +res = 0 +for i in range(M): +    a, b, c = E[i] +    if wf[a - 1][b - 1] != c: +        res += 1 +print(res)