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

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

///s - nodul din care pleca muchia, f - nodul in care ajunge muchia, c - costul muchiei
///ind - vector cu indicii, R - reprezentantii, sol - solutia cu muchiile pe care le alegem
long long n, m, k = 0, s[400005], f[400005], c[400005], ind[400005], R[400005], sol[400005], costMin = 0;

///functie dupa care vreau sa ordonez indicii in functie de costuri (de la cel mai mic la cel mai mare)
bool ordCost(int x, int y)
{
    return c[x] < c[y];
}

///functie care imi calculeaza recursiv reprezentantul fiecarei grupe, stiind ca daca am mai multe componenete conexe fiecare are un
///reprezentant al sau
int reprez(int x)
{
    if(R[x] == x)
        return x;
    R[x] = reprez(R[x]);
    return R[x];
}

///functie care imi reuneste doua componente conexe, facand una singura, cu un singur reprezentant
void reuniune(int x, int y)
{
    R[reprez(x)] = reprez(y);
}

int main()
{
    in>>n>>m;
    ///citesc muchiile (nodurile intre care apare muchia) si costul acesteia
    ///setez vectorul de indici cu valoarea lui i pt pozitia corespunzatoare lui i
    for(long long i = 1; i <= m; i++)
    {
        in>>s[i]>>f[i]>>c[i];
        ind[i] = i;
    }
    ///momentan am n noduri izolate, iar fiecare se are ca reprezentant pe el insusi
    for(long long i = 1; i <= n; i++)
        R[i] = i;
    ///sortez vectorul de indici dupa costul muchiilor
    sort(ind + 1, ind + m + 1, ordCost);
    ///parcurg muchiile in ordinea costurilor minime
    for(long long i = 1; i <= m; i++)
    {
        ///daca reprezentantul nodului de unde pleaca muchia nu este egal cu reprezentantul nodului unde ajunge muchia atunci am doua
        ///componente conexe diferite, deci le pot uni fara a pierde proprietatea de arbore (sa imi apara cicluri)
        if(reprez(s[ind[i]]) != reprez(f[ind[i]]))
        {
            ///adaug costul muchiei la costul minim
            costMin += c[ind[i]];
            ///reunesc cele doua componente conexe
            reuniune(s[ind[i]], f[ind[i]]);
            k++;
            ///introduc in vectorul de solutii valoarea indicelui specific muchiei care imi respecta proprietatea de cost minim si arbore
            sol[k] = ind[i];
        }
    }
    ///afisare
    out<<costMin<<"\n";
    out<<n-1<<"\n";
    for(long long i = 1; i <= k; i++)
        out<<s[sol[i]]<<" "<<f[sol[i]]<<"\n";
    return 0;
}