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

#define infile "apm.in"
#define outfile "apm.out"

struct edge {
    int x, y;
    int price;
};

bool p_cond(const edge& a, const edge& b) {
    return a.price < b.price;
}

std::vector<int> p(200001), sz(200001);

std::ifstream f(infile);
std::ofstream g(outfile);

int Find(const int x) {
    if (x != p[x])
        p[x] = Find(p[x]);
    return p[x];
}

void Union(int x, int y) {
    if (x != y) {
        if (sz[x] < sz[y]) {
            std::swap(x, y);
        }

        sz[x] += sz[y];
        p[y] = x;
        sz[y] = 0;
    }
}

void getData(int & n, int& m, std::vector<edge>& e_) {
    int x, y;
    int price;
    f >> n >> m;
    while (f >> x >> y >> price) {
        e_.push_back(edge{x, y, price});
    };
}

int main() {
    int n(0), m(0);
    std::vector<edge> e, result;
    getData(n, m, e);

    std::ranges::sort(e, p_cond);

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

    long S(0);
    for (const auto& [x, y, price] : e) {
        int a = Find(x);
        int b = Find(y);
        if (a != b) {
            S += price;
            Union(a, b);
            result.push_back({x, y, price});
        }
    }

    g << S << std::endl;
    g << result.size() << std::endl;
    for (const auto& [x, y, price] : result) {
        g << x << " " << y << std::endl;
    }

    f.close();
    g.close();
    return 0;
}