n,m = list(map(int, input().split()))

INF = 1000*n+1

#edges = [[] for _ in  range(m)]

edge = [[INF for _ in range(n)] for _ in range(n)]

d = [[INF for _ in range(n)] for _ in range(n)]



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

for a,b,c in abc:

    

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

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

    



def dijkstra(i):

    #d = [INF for _ in range(n)] 

    d[i][i] = 0

    used = [False] * n



    while True:

        v = -1

        for j in range(n):

            if used[j] == False and (v == -1 or d[i][j] < d[i][v]):

                v = j

        if v == -1:

            break

        used[v] = True

        for k in range(n):



            d[i][k] = min(d[i][k], d[i][v] + edge[v][k])

            d[k][i] = d[i][k]





for i in range(n):

    dijkstra(i)

#print(edge)

#print(d)

ans = 0

for a, b, c in abc:

    if d[a-1][b-1] < c:

        ans += 1



print(ans)

import heapq

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

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



INF = float("inf")

for i in range(M):

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

    a, b = a-1, b-1

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

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





def djkstra(start, n, es):

    # start：スタート地点のノード

    # n：ノード数

    # es：edges, ある辺のコスト



    # 最初は全部未探索

    costs = [INF] * n

    costs[start] = 0

    checked = [False] * n #調べ終わったノードはTrue

    hq = [(0, start)] # スタートからスタートまでのコスト（＝０）とスタートの番号

    heapq.heapify(hq)

    while hq: # キューに残りがある限り

        cost, v = heapq.heappop(hq) # 取り出す

        if checked[v]:

            continue # 既に調べていたら飛ばす

        checked[v] = True

        costs[v] = cost

        for to, c in es[v]: # ノードvから伸びている辺すべてについて

            if costs[to] <= cost + c:

                continue # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす

            heapq.heappush(hq, (cost+c, to)) # toに行くまでの最短距離がcost+cに更新される

        

    return costs





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

for i in range(N):

    min_cost[i] = djkstra(i,N,es)



ans = 0

for i in range(len(es)):

    for to, c in es[i]:

        if min_cost[i][to] < c:

            #print("--------")

            #print(i,to,c)

            ans += 1



print((ans//2))

#print(min_cost)
n, m = list(map(int, input().split()))
INF = 1000 * n + 1
# edges = [[] for _ in  range(m)]
edge = [[INF for _ in range(n)] for _ in range(n)]
d = [[INF for _ in range(n)] for _ in range(n)]
abc = [list(map(int, input().split())) for _ in range(m)]
for a, b, c in abc:
    edge[a - 1][b - 1] = c
    edge[b - 1][a - 1] = c


def dijkstra(i):
    # d = [INF for _ in range(n)]
    d[i][i] = 0
    used = [False] * n
    while True:
        v = -1
        for j in range(n):
            if used[j] == False and (v == -1 or d[i][j] < d[i][v]):
                v = j
        if v == -1:
            break
        used[v] = True
        for k in range(n):
            d[i][k] = min(d[i][k], d[i][v] + edge[v][k])
            d[k][i] = d[i][k]


for i in range(n):
    dijkstra(i)
# print(edge)
# print(d)
ans = 0
for a, b, c in abc:
    if d[a - 1][b - 1] < c:
        ans += 1
print(ans)

import heapq

N, M = list(map(int, input().split()))
es = [[] for _ in range(N)]
INF = float("inf")
for i in range(M):
    a, b, c = list(map(int, input().split()))
    a, b = a - 1, b - 1
    es[a].append((b, c))
    es[b].append((a, c))


def djkstra(start, n, es):
    # start：スタート地点のノード
    # n：ノード数
    # es：edges, ある辺のコスト
    # 最初は全部未探索
    costs = [INF] * n
    costs[start] = 0
    checked = [False] * n  # 調べ終わったノードはTrue
    hq = [(0, start)]  # スタートからスタートまでのコスト（＝０）とスタートの番号
    heapq.heapify(hq)
    while hq:  # キューに残りがある限り
        cost, v = heapq.heappop(hq)  # 取り出す
        if checked[v]:
            continue  # 既に調べていたら飛ばす
        checked[v] = True
        costs[v] = cost
        for to, c in es[v]:  # ノードvから伸びている辺すべてについて
            if costs[to] <= cost + c:
                continue  # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす
            heapq.heappush(hq, (cost + c, to))  # toに行くまでの最短距離がcost+cに更新される
    return costs


min_cost = [[] for _ in range(N)]
for i in range(N):
    min_cost[i] = djkstra(i, N, es)
ans = 0
for i in range(len(es)):
    for to, c in es[i]:
        if min_cost[i][to] < c:
            # print("--------")
            # print(i,to,c)
            ans += 1
print((ans // 2))
# print(min_cost)

-n, m = list(map(int, input().split())) -INF = 1000 * n + 1 -# edges = [[] for _ in  range(m)] -edge = [[INF for _ in range(n)] for _ in range(n)] -d = [[INF for _ in range(n)] for _ in range(n)] -abc = [list(map(int, input().split())) for _ in range(m)] -for a, b, c in abc: -    edge[a - 1][b - 1] = c -    edge[b - 1][a - 1] = c +import heapq + +N, M = list(map(int, input().split())) +es = [[] for _ in range(N)] +INF = float("inf") +for i in range(M): +    a, b, c = list(map(int, input().split())) +    a, b = a - 1, b - 1 +    es[a].append((b, c)) +    es[b].append((a, c)) -def dijkstra(i): -    # d = [INF for _ in range(n)] -    d[i][i] = 0 -    used = [False] * n -    while True: -        v = -1 -        for j in range(n): -            if used[j] == False and (v == -1 or d[i][j] < d[i][v]): -                v = j -        if v == -1: -            break -        used[v] = True -        for k in range(n): -            d[i][k] = min(d[i][k], d[i][v] + edge[v][k]) -            d[k][i] = d[i][k] +def djkstra(start, n, es): +    # start：スタート地点のノード +    # n：ノード数 +    # es：edges, ある辺のコスト +    # 最初は全部未探索 +    costs = [INF] * n +    costs[start] = 0 +    checked = [False] * n  # 調べ終わったノードはTrue +    hq = [(0, start)]  # スタートからスタートまでのコスト（＝０）とスタートの番号 +    heapq.heapify(hq) +    while hq:  # キューに残りがある限り +        cost, v = heapq.heappop(hq)  # 取り出す +        if checked[v]: +            continue  # 既に調べていたら飛ばす +        checked[v] = True +        costs[v] = cost +        for to, c in es[v]:  # ノードvから伸びている辺すべてについて +            if costs[to] <= cost + c: +                continue  # 現時点で発覚しているtoまでのコストのほうが、v経由でto行くまでのコストより小さいなら更新せず飛ばす +            heapq.heappush(hq, (cost + c, to))  # toに行くまでの最短距離がcost+cに更新される +    return costs -for i in range(n): -    dijkstra(i) -# print(edge) -# print(d) +min_cost = [[] for _ in range(N)] +for i in range(N): +    min_cost[i] = djkstra(i, N, es) -for a, b, c in abc: -    if d[a - 1][b - 1] < c: -        ans += 1 -print(ans) +for i in range(len(es)): +    for to, c in es[i]: +        if min_cost[i][to] < c: +            # print(i,to,c) +            ans += 1 +print((ans // 2)) +# print(min_cost)