#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[400006],lg,sol;
bool comp(strct a,strct b)
{
    if (a.dist<b.dist) return 1;
    if (a.dist>b.dist) return 0;
    if (a.nod1<b.nod1) return 1;
    if (a.nod1>b.nod1) return 0;
    return a.nod2<b.nod2;
}

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;
        long long tata1=reprez(el1);
        long long tata2=reprez(el2);
        if (tata1==tata2) continue;
        tata[tata2]=tata1;
        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;
}