#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchii
{
    int nod_x, nod_y, cost;

}muchie[100001], arbore[100001];

int parinte[100001], n, m, suma_cost_minim, contor;

bool comparare(muchii a, muchii b)
{
    return a.cost < b.cost;
}

int cautare_strastramos(int nod)
{
    if(parinte[nod]==nod)
        return nod;
    else
     return parinte[nod]=cautare_strastramos(parinte[nod]);
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=m; i++)
        fin >> muchie[i].nod_x >> muchie[i].nod_y >> muchie[i].cost;
    sort(muchie+1, muchie+m+1, comparare);
    for(int i=1; i<=n; i++)
        parinte[i]=i;
    for(int i=1; i<=m; i++)
        if(cautare_strastramos(muchie[i].nod_x)!=cautare_strastramos(muchie[i].nod_y))
        {
            arbore[++contor]=muchie[i];
            suma_cost_minim+=muchie[i].cost;
            parinte[cautare_strastramos(muchie[i].nod_y)]=cautare_strastramos(muchie[i].nod_x);

        }
    fout << suma_cost_minim<<'\n';
    fout << n-1 <<'\n';
    for(int i=1; i<=contor; i++)
        fout << arbore[i].nod_y<<' '<< arbore[i].nod_x <<'\n';


}