#include <fstream>
#include <utility>
#include <algorithm>

int paduri[200001], rang[200001];
struct muchie {
    int from, to;
    int cost;
} muchii[400000], sol[200000];

void unite(int x, int y) {
    if (rang[x] > rang[y]) {
        paduri[y] = x;
    } else {
        paduri[x] = y;
    }

    if (rang[x] == rang[y]) {
        rang[y]++;
    }
}

int find(int x) {
    int root;
    for (root = x; paduri[root] != root; root = paduri[root]);

    while (paduri[x] != x) {
        int y = paduri[x];
        paduri[x] = root;
        x = y;
    }

    return root;
}

int main() {
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");
    int n, m;

    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        paduri[i] = i;
        rang[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        fin >> muchii[i].from >> muchii[i].to >> muchii[i].cost;
    }
    std::sort(muchii, muchii + m, [](const muchie& a, const muchie& b) {
        return a.cost < b.cost;
    });
    int s = 0, sum = 0;
    for (int i = 0; i < m; i++) {
        if (find(muchii[i].from) != find(muchii[i].to)) {
            sol[s] = muchii[i];
            s++;
            sum += muchii[i].cost;
            unite(find(muchii[i].from), find(muchii[i].to));
        }
    }
    fout << sum << '\n' << s << '\n';
    for (int i = 0; i < s; i++) {
        fout << sol[i].from << ' ' << sol[i].to << '\n';
    }
    return 0;
}