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

using namespace std;

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

int costAPM, tata[200001], inaltime[200001];

struct muchie {
    int sursa, destinatie, cost;
} u[400001];

bool comp(muchie a, muchie b) {
    return a.cost < b.cost;
}

int reprezentant_tata(int nod) {///cautam nodul sursa ,nu tatal direct
    while (tata[nod] != nod)
        nod = tata[nod];
    return nod;
}

// regula: intotdeauna vom unii arborele de inaltime mai mica de arborele cu inaltime mai mare
void reuneste(int tataSursa, int tataDestinatie) {
    if (inaltime[tataSursa] > inaltime[tataDestinatie])
        tata[tataDestinatie] = tataSursa;
    else if (inaltime[tataSursa] < inaltime[tataDestinatie])
        tata[tataSursa] = tataDestinatie;
    else if (inaltime[tataSursa] == inaltime[tataDestinatie]) {
        tata[tataSursa] = tataDestinatie;
        inaltime[tataDestinatie]++;
    }
}

void kruskal() {
    vector<pair<int, int>> apm;
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;
    for (int i = 1; i <= nrMuchii; i++)
        fin >> u[i].sursa >> u[i].destinatie >> u[i].cost;
    sort(u + 1, u + nrMuchii + 1, comp); // sortez crescator muchiile dupa cost
    for (int i = 1; i <= nrMuchii; i++) {
        tata[i] = i;
        inaltime[i] = 1;
    }
    for (int i = 1; i <= nrMuchii; i++) {
        int tataSursa = reprezentant_tata(u[i].sursa); // caut reprezentantul nodului sursa curent
        int tataDestinatie = reprezentant_tata(u[i].destinatie); // caut reprezentantantul nodului destinatie curent
        if (tataSursa != tataDestinatie) {
            // daca nu am acelasi tata inseamna ca pot sa reunesc
            reuneste(tataSursa, tataDestinatie);
            apm.push_back(make_pair(u[i].sursa, u[i].destinatie));
            costAPM += u[i].cost;
        }
    }
    nrMuchii = nrNoduri - 1; // stim ca un APM are intotdeuna nrNoduri - 1 muchii
    fout << costAPM << "\n" << nrMuchii << "\n";
    for (auto i: apm)
        fout << i.first << " " << i.second << "\n";
}

int main() {
    kruskal();
    return 0;
}