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

using namespace std;

struct Muchie {
    int x, y, cost;

    bool operator<(const Muchie& rhs) const {
        return cost < rhs.cost;
    }
};

vector<int> tati, grad;

int find_father(int nod) {
    if (tati[nod] == nod) {
        return nod;
    } else {
        return tati[nod] = find_father(tati[nod]);
    }
}

bool connected(int x, int y) {
    int tata_x = find_father(x);
    int tata_y = find_father(y);

    return tata_x == tata_y;
}

void connect(int x, int y) {
    int tata_x = find_father(x);
    int tata_y = find_father(y);
    if (tata_x != tata_y) {
        if (grad[tata_x] < grad[tata_y]) {
            tati[tata_x] = tata_y;
            grad[tata_y] += grad[tata_x];
        } else {
            tati[tata_y] = tata_x;
            grad[tata_x] += grad[tata_y];
        }
    }
}

int main()
{
    ifstream in("apm.in");
    int n, m;
    in >> n >> m;

    tati.resize(n);
    iota(tati.begin(), tati.end(), 0);

    grad.resize(n, 1);

    vector<Muchie> muchii;
    muchii.reserve(m);

    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        in >> x >> y >> cost;
        --x;
        --y;

        muchii.push_back({ x, y, cost });
        muchii.push_back({ y, x, cost });
    }

    sort(muchii.begin(), muchii.end());

    vector<Muchie> apm;
    apm.reserve(n - 1);

    int suma = 0;

    auto it = muchii.cbegin();
    while (it != muchii.cend()) {
        auto m = *it;

        int x = m.x, y = m.y;

        if (!connected(x, y)) {
            connect(x, y);
            suma += m.cost;
            apm.push_back(m);
        }

        ++it;
    }

    ofstream out("apm.out");
    out << suma << '\n' << apm.size() << '\n';
    for (const auto& muchie : apm) {
        out << (muchie.x + 1) << ' ' << (muchie.y + 1) << '\n';
    }
}