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