prim.cpp

// Author: Sander de Beet

#include <bits/stdc++.h>  // This will work only for g++ compiler.

#define f0r(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define f1r(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define f0rr(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define f1rr(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based

// short hand for usual tokens
#define pb push_back
#define fi first
#define se second

// to be used with algorithms that processes a container Eg: find(all(c),42)
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal

// find if a given value is present in a container. Container version. Runs in log(n) for set and map
#define present(c,x) ((c).find(x) != (c).end())

// find version works for all containers. This is present in std namespace.
#define cpresent(c,x) (find(all(c),x) != (c).end())

#define uni(x) (x).erase(unique(all(x)), (x).end())
#define debug(x) cout<<#x<<" -> "<<x<<'\n'

using namespace std;

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;


void fast_IO() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

void solve() {
    int n, m; cin >> n >> m;
    int mst_cost = 0;

    vector<pair<int, int>> adj[n];
    vector<int> vis(n, 0);
    vector<int> key(n, INT_MAX);
    vector<int> parent(n, -1);

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }

    priority_queue<ii, vector<ii>, greater<ii>> pq;

    // {cost, node}
    pq.push({0LL, 0});

    while (!pq.empty()) {
        ii item = pq.top(); pq.pop();

        int cost = item.first;
        int node = item.second;

        if (!vis[node]) {
            mst_cost += cost;
            vis[node] = 1;

            for (auto npair : adj[node]) {
                int weight = npair.fi;
                int nb = npair.second;

                if (!vis[nb] && weight < key[nb]) {
                    key[nb] = weight;
                    pq.push(npair);
                    parent[nb] = node;
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (parent[i] != -1) {
            cout << parent[i] << " " << i << "\n";
        }
    }

    cout << mst_cost << "\n";
}


int main(int argc, char* argv[]) {
    fast_IO();
    auto a = freopen(argv[1], "r", stdin);

    solve();

    return 0;
}