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

ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct Muchie { int nod_1 , nod_2 , cost; } muchii[400001];
int grad[200001] , radacina[200001];
bool inclus[400001];

int Radacina (const int nod_actual)
{
    return radacina[nod_actual] ? (radacina[nod_actual] = Radacina(radacina[nod_actual])) : nod_actual;
}

void Unire (const int nod_1 , const int nod_2)
{
    if (grad[nod_1] < grad[nod_2])
        { radacina[nod_1] = nod_2; }
    else
        if (grad[nod_1] > grad[nod_2])
            { radacina[nod_2] = nod_1; }
    else
        { radacina[nod_1] = nod_2; grad[nod_2]++; }
}

int main ()
{
    int numar_noduri , numar_muchii;
    cin >> numar_noduri >> numar_muchii;

    for (int indice = 1 ; indice <= numar_muchii ; indice++)
        { cin >> muchii[indice].nod_1 >> muchii[indice].nod_2 >> muchii[indice].cost; }

    sort(muchii + 1 , muchii + numar_muchii + 1 , [] (Muchie optiune_1 , Muchie optiune_2) -> bool { return optiune_1.cost < optiune_2.cost; });

    int cost_total = 0;
    for (int indice = 1 ; indice <= numar_muchii ; indice++) {
        const int radacina_1 = Radacina(muchii[indice].nod_1) , radacina_2 = Radacina(muchii[indice].nod_2);
        if (radacina_1 != radacina_2) { Unire(radacina_1 , radacina_2); cost_total += muchii[indice].cost; inclus[indice] = true; }
    }

    cout << cost_total << '\n' << numar_noduri - 1 << '\n';

    for (int indice = 1 ; indice <= numar_muchii ; indice++) 
        { if (inclus[indice]) { cout << muchii[indice].nod_1 << ' ' << muchii[indice].nod_2 << '\n'; } }

    cout.close(); cin.close();
    return 0;
}