//
// Created by h4rapa1b on 11/11/25.
//

#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

struct edge {
    int u, v, cost;
};

vector<int> parent;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

bool unite(int x, int y) {
    const int px = find(x);
    const int py = find(y);

    if (px == py) {
        return false;
    }

    parent[px] = py;
    return true;
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    if (!fin.is_open()) return 1;

    int n, m;
    vector<edge> edges;
    vector<edge> mst;
    int total_cost = 0;

    fin >> n >> m;

    parent.resize(n + 1);
    edges.resize(m);

    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    for (int i = 0; i < m; ++i) {
        fin >> edges[i].u >> edges[i].v >> edges[i].cost;
    }
    sort(edges.begin(), edges.end(), [](const edge &a, const edge &b) {
        return a.cost < b.cost;
    });

    for (const edge &e : edges) {
        if (unite(e.u, e.v)) {
            mst.push_back(e);
            total_cost += e.cost;
        }
    }

    fout<<total_cost<<endl;
    fout<<mst.size()<<endl;
    for (const edge &e : mst) {
        fout << e.v << " " << e.u << endl;
    }

    return 0;
}