#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
long n,ar,nrr,k,t[200007],h[200007],m[3][200007],sol[2][200007];
void citire()
{
    ifstream f("apm.in"); f>>n>>ar;
    for(k=0;k<ar;k++)f>>m[0][k]>>m[1][k]>>m[2][k];
    f.close();
}
int cmpmm(const void *a,const void *b)
{
    return((int*) a)[2]-((int*) b)[2];
}
int arb(int nd)
{
    while(t[nd])nd=t[nd];
    return nd;
}
int main()
{
    ofstream g("apm.out");
    citire();
    qsort(m,ar,sizeof(m[0]),cmpmm);
    k=0; long rr=0,cost=0;
    do
    {while(arb(m[0][k])==arb(m[1][k]))k++;
        nrr++;
        sol[0][rr]=m[0][k]; sol[1][rr]=m[1][k];
        rr++; cost+=m[2][k];
        if(h[m[0][k]]==h[m[1][k]])
        {t[m[0][k]]=m[1][k];
        h[m[1][k]]++;}
        else
            if(h[m[0][k]]<h[m[1][k]])t[m[0][k]]=m[1][k];
            else t[m[1][k]]=m[0][k];
        k++;
    }while(nrr<n-1);
    g<<cost<<'\n'<<rr+1<<'\n';
    for(int i=0;i<rr;i++)g<<sol[0][i]<<" "<<sol[1][i]<<'\n';
    g.close();
    return 0;
}