graph_t compute_Prims_MST_fast(const graph_t & graph)
{
    auto vertices = graph.vertices();
    std::list<int> vertices_in_MST = { *vertices.begin() };
    graph_t MST;

    auto cheapest_edge_vertex = [&](int vertex) {
        return *std::min_element(vertices_in_MST.begin(), vertices_in_MST.end(),
                                [&](int lhs, int rhs) {
                                    return graph.weight(lhs, vertex) < graph.weight(rhs, vertex);
                                });
    };

    auto compare_vertices = [&](int lhs, int rhs) {
        return graph.weight(lhs, cheapest_edge_vertex(lhs)) > graph.weight(rhs, cheapest_edge_vertex(rhs));
    };

    std::priority_queue<int, std::vector<int>, std::function<bool (int, int)>> pq(
            std::next(vertices.begin()), vertices.end(), compare_vertices
    );

    while (!pq.empty()) {
        auto v = pq.top();
        auto u = cheapest_edge_vertex(v);
        auto weight = graph.weight(u, v);

        if (weight != std::numeric_limits<double>::infinity()) {
            MST.add_edge(u, v, weight);
            vertices_in_MST.push_back(v);
        }

        pq.pop();
    }

    return MST;
};