Prim's algorithm providing inconsistent results

Question

I'm implementing Prim's algorithm for finding a minimum spanning tree in a graph. I have implemented it using a priority_queue in STL. The issue is that I get a correct MST for some test cases and a wrong one for others.

My input is an adjacency list representation of a graph. The first line of the text file contains the number of vertices in the graph. Each subsequent line contains information about adjacent vertices for a specific graph vertex. Each line starts with the index of the vertex, followed by pairs of numbers that correspond to the indices of neighboring vertices and the weights of the edges connecting them to the current vertex.

The algorithm works correctly for the following test case:

9
0 1 4 7 8
1 2 8 7 11
2 3 7 8 2 5 4
3 4 9 5 14
4 5 10 
5 6 2
6 7 1 8 6
7 8 7

Meanwhile, it calculates a wrong MST for this graph:

9
0 8 18 6 1 4 10 7 7
6 4 6 1 20
4 1 3 7 5
1 3 12
3 8 4 2 9
2 5 2 
8 2 15 5 8

My implementation of the algorithm:

void MST::getMST() {
    const int n = graph.adjacencyList.size();
    std::vector<bool> visited(n, false);
    std::vector<int> parent(n, -1);
    std::vector<int> key(n, std::numeric_limits<int>::max());

    // Start from vertex 0
    key[0] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        if (parent[u] != -1) {
            edges.push_back({parent[u], u});
        }
        for (const auto& [v, weight] : graph.adjacencyList[u]) {
            if (!visited[v] && weight < key[v]) {
                key[v] = weight;
                pq.push({key[v], v});
                parent[v] = u;
            }
        }
    }
}

A function to read a graph from a file:

void Graph::readGraphFromFile(const std::string& filename) {
    std::ifstream inFile(filename);
    if (!inFile) {
        std::cerr << "Unable to open the file: " << filename << std::endl;
        return;
    }

    // Read vertex count
    inFile >> vertexCount;
    adjacencyList.resize(vertexCount);

    // Read edges
    std::string line;
    std::getline(inFile, line); // Read the rest of the line after vertexCount
    while (std::getline(inFile, line)) {
        std::istringstream lineStream(line);
        int vertex, neighbor, weight;
        lineStream >> vertex;
        while (lineStream >> neighbor >> weight) {
            adjacencyList[vertex].push_back(std::make_pair(neighbor, weight));
        }
    }

    inFile.close();
}

// Constructor initializes the MST object with the input graph
MST::MST(const Graph& g){
    graph = g;
}

A function to save edges of a MST in a file:

// Saves the Minimum Spanning Tree edges to a file
void MST::saveToFile(const std::string& filename) const {
    std::ofstream outFile(filename);
    if (!outFile) {
        std::cerr << "Unable to open the file: " << filename << std::endl;
        return;
    }

    for (const auto& edge : edges) {
        outFile << edge.first << " -- " << edge.second << std::endl;
    }

    outFile.close();
}

Where could I go wrong here?