#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("apm.in");
ofstream fo ("apm.out");
struct strct{

long long nod1,nod2,dist;
} muchie[400006],solutie[400006];
long long nrnod,nrmuchii,tata[200006],lg,sol;
bool comp(strct a,strct b)
{
    return a.dist<=b.dist;
}

long long reprez(int nod)
{
    if (tata[nod]==nod) return nod;
    else return tata[nod]=reprez(tata[nod]);
}
int main()
{
    fi>>nrnod>>nrmuchii;
    for (int i=1;i<=nrmuchii;i++)
        fi>>muchie[i].nod1>>muchie[i].nod2>>muchie[i].dist;
    sort(muchie+1,muchie+nrmuchii+1,comp);
    for (int i=1;i<=nrnod;i++) tata[i]=i;
    for (int i=1;i<=nrmuchii;i++)
    {
        long long el1=muchie[i].nod1;
        long long el2=muchie[i].nod2;
        if (reprez(el1)==reprez(el2)) continue;
        tata[reprez(el2)]=reprez(el1);
        lg++;
        solutie[lg].nod1=el1;
        solutie[lg].nod2=el2;
        sol+=muchie[i].dist;
    }
    fo<<sol<<'\n'<<nrnod-1<<'\n';
    for (int i=1;i<=lg;i++) fo<<solutie[i].nod1<<' '<<solutie[i].nod2<<'\n';
    return 0;
}