#include<stdio.h>
struct nod
{
	int vecin,cost;
	nod *adr;
};
nod *v[200001],*p;
void adaug(nod *&L,int v,int c)
{
	nod *p;
	p=new nod;
	p->vecin=v;
	p->cost=c;
	p->adr=L;
	L=p;
}
int N,M,i,x,y,c,k,vmin,s,d[200001],t[200001],viz[200001];
int main()
{
	freopen("apm.in","rt",stdin);
	freopen("apm.out","wt",stdout);
	scanf("%d %d",&N,&M);
	for(i=1;i<=N;i++)
	{
		v[i]=0;
	}
	for(i=1;i<=M;i++)
	{
		scanf("%d %d %d",&x,&y,&c);
		adaug(v[x],y,c);
		adaug(v[y],x,c);
	}
	for(i=1;i<=N;i++)
	{
		d[i]=1000000000;
		t[i]=0;
		viz[i]=0;
	}
	viz[1]=1;
	d[1]=0;
	for(p=v[1];p!=0;p=p->adr)
	{
		d[p->vecin]=p->cost;
		t[p->vecin]=1;
	}
	s=0;
	for(k=1;k<=N-1;k++)
	{
		vmin=1000000000;
		for(i=1;i<=N;i++)
		{
			if(viz[i]==0 && d[i]<vmin)
			{
				x=i;
				vmin=d[i];
			}
		}
		viz[x]=1;
		s=s+d[x];
		for(p=v[x];p!=0;p=p->adr)
		{
			if(d[p->vecin]>p->cost)
			{
				d[p->vecin]=p->cost;
				t[p->vecin]=x;
			}
		}
	}
	printf("%d \n",s);
	printf("%d \n",N-1);
	for(i=2;i<=N;i++)
	{
		printf("%d %d \n",t[i],i);
	}
	fclose(stdout);
	return 0;
}