Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

rest_edges = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        rest_edges.add((a, b))

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        if (a,b) not in rest_edges:
            continue
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        last_n = shortest[-1]
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))
            
            del_x, del_y = min(x, last_n), max(x, last_n)
            rest_edges.discard((del_x, del_y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Fixed submission:
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))

edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Fixed submission:
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

shotest_set = set()
for a in range(1, N+1):
    for b in range(a+1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Fixed submission:
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

shotest_set = set()
for a in range(1, N+1):
    for b in range(1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            shotest_set.add((x,y))

#print(edges)
#print(shotest_set)
print(len(edges) - len(shotest_set))

Fixed submission:
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
    
edges = ABC[:]

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = 1000*1000*10
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

#print(edges)
# 無効グラフなので逆向きのエッジも作る
rev_edges = [ (b,a,c) for a,b,c in edges ]
graph = Graph(edges + rev_edges)

rest_edges = set([(a,b) for a,b,c in edges])
for a in range(1, N+1):
    for b in range(1, N+1):
        shortest = graph.dijkstra(a, b)
        shortest = list(shortest)
        #print(shortest)
        for x, y in zip(shortest[:-1],shortest[1:]):
            x, y = min(x, y), max(x, y)
            #print(x, y)
            rest_edges.discard((x,y))
            
print(len(rest_edges))

Fixed submission:
N, M = map(int, input().split())

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a, b, c))
edges = ABC[:]

graph = {}
for a,b,c in edges:
    if not a in graph:
        graph[a] = {}
    if not b in graph:
        graph[b] = {}
    graph[a][b] = c
    graph[b][a] = c


from heapq import heappush, heappop

def dijkstra(graph, start):
    A = [None] * (N+1)
    queue = [(0, start)]
    while queue:
        path_len, v = heappop(queue)
        if A[v] is None: # v is unvisited
            A[v] = path_len
            for w, edge_len in graph[v].items():
                if A[w] is None:
                    heappush(queue, (path_len + edge_len, w))

    # to give same result as original, assign zero distance to unreachable vertices             
    return [0 if x is None else x for x in A]

shrtest = [[0]*(N+1)]
for a in range(1, N+1):
    sub_shrtest = dijkstra(graph, a)
    shrtest.append(sub_shrtest)
#print(shrtest)

ans = 0
for a,b,c in edges:
    if shrtest[a][b] != c:
        ans += 1
print(ans)