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

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

#define NMAX 200005

int n, m, sol, tata[NMAX], adan[NMAX];
bool viz[NMAX];
vector<pair<int, pair<int, int>>> G;
vector<pair<int, int>> sol_muchii;

void citire() {
    f >> n >> m;
    int x, y, c;
    for (int i = 0; i < m; ++i) {
        f >> x >> y >> c;
        G.push_back({c, {x, y}});
    }
    sort(G.begin(), G.end());
}

void initializare_paduri() {
    for (int i = 1; i <= n; i++)
        tata[i] = i;
}

int radacina(int x) {
    if (tata[x] == x)
        return x;
    int rad = radacina(tata[x]);
    tata[x] = rad;
    return rad;
}

void reunire(int x, int y) {
    int rad1 = radacina(x), rad2 = radacina(y);
    if (adan[rad1] > adan[rad2])
        tata[rad2] = rad1;
    else {
        tata[rad1] = rad2;
        adan[rad2] = max(adan[rad2], adan[rad1] + 1);
    }
}

void prelucrare() {
    for (auto &muchie: G) {
        if (radacina(muchie.second.first) == radacina(muchie.second.second))
            continue;
        sol += muchie.first;
        sol_muchii.push_back(muchie.second);
        reunire(muchie.second.first, muchie.second.second);
    }
}

void afisare() {
    g << sol << '\n' << sol_muchii.size();
    for (auto &muchie: sol_muchii) {
        g << '\n' << muchie.first << ' ' << muchie.second;
    }
}

int main() {
    citire();
    initializare_paduri();
    prelucrare();
    afisare();
    return 0;
}