Как уменьшить память алгоритма Прима

Делаю алгоритм Прима через матрицу смежности

def main():
    n, m = map(int, input().split())

    graph = [[float("-inf") for _ in range(n)] for _ in range(m)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        if w > graph[u - 1][v - 1]:
            graph[u - 1][v - 1] = w

        if w > graph[v - 1][u - 1]:
            graph[v - 1][u - 1] = w

    print(graph)
    import sys
    print(sys.getsizeof(graph))
    # prim(n, graph)


def prim(N, graph):
    selected = [0 for i in range(N)]
    edge_visited = 0  # флаг того, что непосещенных ребер в графе не осталось
    selected[0] = True

    final_weight = 0
    while edge_visited < N - 1:
        maximum = float("-inf")
        # a и b запоминают индексы graph[m][n], то есть индекс минимального веса
        a = 0
        b = 0
        for vertex in range(N):
            # если мы посетили вершину ранее, то перебираем её смежные вершины
            if selected[vertex]:
                for adjacent in range(N):
                    # если смежная вершина не находится в посещенных вершинах
                    if not selected[adjacent] and graph[vertex][adjacent]:
                        if maximum < graph[vertex][adjacent]:
                            maximum = graph[vertex][adjacent]
                            a = vertex
                            b = adjacent
        final_weight += graph[a][b]
        selected[b] = True
        edge_visited += 1

    print(final_weight)


if __name__ == "__main__":
    main()

Не проходит по памяти
Думал через списки смежности, но в 3 раза больше памяти занимает

def main():
    n, m = map(int, input().split())

    graph = defaultdict(list)
    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    print(graph)
    print(sys.getsizeof(graph))

Как ускорить по памяти