C++ Prim PQ O((M+N) * logN)

#include <bits/stdc++.h>
#define NMAX 200002
using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

int N, M, x, y, cost;
long long ans = 0;

vector<pair<int, int>> v[NMAX];
int d[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
unordered_set<int> visited;
unordered_map<int, int> edges; // maps vertex to edge w/ min cost

int main() {

    f >> N >> M;
    for (int i = 0; i < M; ++i) {
        f >> x >> y >> cost;
        v[x].push_back({cost, y});
        v[y].push_back({cost, x});
    }

    for (int i = 1; i <= N; ++i)
        d[i] = INT_MAX;
    d[1] = 0;

    pq.push({0, 1});


    while (!pq.empty()) {
        int node = pq.top().second;
        pq.pop();
        visited.insert(node);


        for (pair<int, int> neigh_pr: v[node]){
            int neigh = neigh_pr.second;
            int new_cost = neigh_pr.first;
            if (visited.find(neigh) == visited.end() && new_cost < d[neigh])
            {
                d[neigh] = new_cost;
                pq.push({new_cost, neigh});
                edges[neigh] = node;
            }
        }
    }

    for (int i = 1; i <= N; ++i)
        ans += d[i];

    g << ans << '\n';
    g << N - 1 << '\n';
    for (const auto& edge: edges)
        g << edge.first << ' ' << edge.second << '\n';

    return 0;
}