#include<fstream>
#define M 2000000000;
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,s,viz[200001],t[200001],mini;
struct nod
{
    int v;
    short c;
    nod* leg;
};
typedef nod* PNod;
PNod L[200000],p;
void add(int x,int y,int z)
{
    p=new nod;
    p->v=y;
    p->c=z;
    p->leg=L[x];
    L[x]=p;
         
}
void citire()
{
    int x,y,z,i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {   f>>x>>y>>z;
        add(x,y,z);add(y,x,z);
    }
}
int main()
{   int k,i,poz,nrl,d,d1,d2;
     
    citire();
    nrl=0;s=0;
    for(i=2;i<=n;i++)
        viz[i]=1;
    for(k=1;k<=n-1;k++)
    {
        mini=M;
        for(i=1;i<=n;i++)
            if(viz[i])
			{
				d=M;
				for( p=L[viz[i]];p&&p->v!=i;p=p->leg);
					if(p)d=p->c;
				if(mini>d){poz=i;mini=d;}
			}
        nrl++;
        s+=mini;
        t[poz]=viz[poz];
        for(i=1;i<=n;i++)
            if(viz[i])
			{
				d1=M;d2=M;
				for(p=L[i];p&&p->v!=viz[i];p=p->leg);
				if(p)d1=p->c;
				for(p=L[i];p&&p->v!=poz;p=p->leg);
				if(p)d2=p->c;
			//c[i][viz[i]]>c[i][poz])
				if(d1>d2)viz[i]=poz;
			}
            viz[poz]=0;
    }
    g<<s<<"\n"<<nrl<<"\n";
    for(i=2;i<=nrl+1;i++)
        g<<i<<" "<<t[i]<<"\n";
    return 0;
}