//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");

//varianta cu n^2, vector de culori, se schimba find si union

int Find(int nod) {
    if (tt[nod] != nod) {
        tt[nod] = Find(tt[nod]); // compresie de cale
    }
    return tt[nod];
}

void Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);
    if (root_x == root_y) return;

    if (r[root_x] > r[root_y]) {
        tt[root_y] = root_x;
    }
    else {
        tt[root_x] = root_y;
        if (r[root_x] == r[root_y]) {
            r[root_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}});
    }

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

    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;
}