//de lucrat din urma

//kruskal apm infoarena
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int n, m, cost_total;
vector<pair<int, pair<int, int>>> muchii;
vector<pair<int, int>> apcm;
vector<int> tt;
vector<int> r; //rang
ifstream fin("apm.in");
ofstream fout("apm.out");

int Find(int nod) {
    while (tt[nod] != 0) {
        nod = tt[nod];
    }
    return nod;
}

void Union(int x, int y) {
    int tt_x = tt[x];
    int tt_y = tt[y];
    if (r[tt_x] > r[tt_y]) {
        tt[tt_y] = tt_x;
    }
    else {
        tt[tt_x] = tt_y;
        if (r[tt_x] == r[tt_y]) {
            r[tt_y]++;
        }
    }
}

void Afisare() {
    fout << cost_total << "\n" << apcm.size() << "\n";
    for (auto m : apcm) {
        fout << m.first << " " << m.second << "\n";
    }
}

int main() {
    fin >> n >> m;
    tt.assign(n + 1, 0);
    r.assign(n + 1, 0);
    //muchii.resize(m);

    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back({c, {x, y}});
    }

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

    int cost, x, y;
    for (auto muchie : muchii) {
        cost = muchie.first;
        x = muchie.second.first;
        y = muchie.second.second;
        if (Find(x) != Find(y)) {
            Union(x, y);
            apcm.push_back({x, y});
            cost_total += cost;
            if (apcm.size() == n - 1) {
                break;
            }
        }
    }

    Afisare();
    return 0;
}