#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie{
    int nod1, nod2, cost;
};

vector<muchie> v;
vector<pair<int, int>> sol;
int sefi[200001], cost_total;

bool cmp(muchie x, muchie y) {
    if (x.cost < y.cost) {
        return true;
    }
    return false;
}

int sef_suprem(int x) {
    if (sefi[x] == x) {
        return x;
    } else {
        return sefi[x] = sef_suprem(sefi[x]);
    }
}

void unire(int x, int y) {
    int sef1 = sef_suprem(x);
    int sef2 = sef_suprem(y);
    sefi[sef1] = sef2; //nu coteaza fleul in care legi arborii intre ei
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back({x, y, c});
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 1; i <= n; ++i) {
        sefi[i] = i;
    }
    int i = 0;
    while (sol.size() < n - 1) {
        int nod1 = v[i].nod1;
        int nod2 = v[i].nod2;
        int cost_muchie = v[i].cost;
        if (sef_suprem(nod1) != sef_suprem(nod2)) {
            unire(nod1, nod2);
            sol.push_back({nod1, nod2});
            cost_total += cost_muchie;
        }
        ++i;
    }
    fout << cost_total << '\n' << sol.size() << '\n';
    for (int i = 0; i < sol.size(); ++i) {
        fout << sol[i].first << ' ' << sol[i].second << '\n';
    }
    return 0;
}