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

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

int n, m;
int t[200005];
std::vector<std::tuple<int, int, int>> L;
std::vector<std::pair<int, int>> answer;

void Union(int x, int y) {
    t[x] = y;
}
int FindRoot(int x) {
    int y, root = x;
    while (t[root] != 0) {
        root = t[root];
    }
    while (x != root) {
        y = t[x];
        t[x] = root;
        x = y;
    }

    return root;
}

bool cmp(std::tuple<int, int, int> A, std::tuple<int, int, int> B) {
    return std::get<2>(A) < std::get<2>(B);
}

int main() {
    int x, y, c, rx, ry, costTotal(0);
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        L.push_back(std::make_tuple(x, y, c));
    }

    sort(L.begin(), L.end(), cmp);
    for (auto& w : L) {
        auto[x, y, c] = w;
        rx = FindRoot(x); ry = FindRoot(y);
        if (rx != ry) {
            Union(rx, ry);
            costTotal += c;
            answer.push_back(std::make_pair(x, y));
        }
    }

    fout << costTotal << "\n" << answer.size() << "\n";
    for (auto& w : answer) {
        fout << w.first << " " << w.second << "\n";
    }
    fout.close();
}