#include <bits/stdc++.h>

#define INF ((int)1e9)
#define NMAX ((int)2e5)

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct full_edge {
    int src, dest, cost;
};

int n, m;
vector<full_edge> edges;
vector<full_edge> apm;

int conex_comp[NMAX + 1];
int conex_rank[NMAX + 1];

int get_root(int node) {
    if (conex_comp[node] == node) {
        return node;
    }

    int new_root = get_root(conex_comp[node]);
    conex_comp[node] = new_root;
    return new_root;
}

int unite(int a, int b) {
    int root_a = get_root(a);
    int root_b = get_root(b);

    if (root_a == root_b) {
        // The nodes are already in the same component
        return -1;
    }

    // Otherwise, connect the graphs
    if (conex_rank[root_a] < conex_rank[root_b]) {
        conex_comp[root_a] = root_b;
    } else {
        conex_comp[root_b] = root_a;
    }

    if (conex_rank[root_a] == conex_rank[root_b]) {
        ++conex_rank[root_b];
    }

    return 0;
}

int main(void) {
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int src, dest, cost;
        fin >> src >> dest >> cost;

        edges.push_back({src, dest, cost});
    }

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

    sort(edges.begin(), edges.end(), [](full_edge &a, full_edge &b) {
        return a.cost < b.cost;
    });

    int cost = 0;
    for (size_t i = 0; i < edges.size(); ++i) {
        full_edge curr = edges[i];
        if (unite(curr.src, curr.dest) == -1) {
            continue;
        }

        cost += curr.cost;
        apm.push_back(curr);
    }

    fout << cost << "\n" << n - 1 << "\n";
    for (size_t i = 0; i < apm.size(); ++i) {
        fout << apm[i].dest << " " << apm[i].src << "\n";
    }

    return 0;
}