#include<stdio.h>
#define Inf 1<<30
#define Nmax 200010

struct lista {int inf,cost; lista *adr;} *v[Nmax],*p;

int cst,x,y,C[Nmax],H[Nmax],i,j,n,m,Cost,Arb[Nmax],T[Nmax],N,nod,L,poz[Nmax];

void add(int i, int j, int cst)
{
	lista *c;
	c=new lista;
	c->inf=j;
	c->cost=cst;
	c->adr=v[i];
	v[i]=c;	
}

void swap(int i, int j)
{
	int aux;
	aux=H[poz[i]]; H[poz[i]]=H[poz[j]]; H[poz[j]]=aux;
	aux=poz[i]; poz[i]=poz[j]; poz[j]=aux;
}

int pmin(int i)
{
	if( (i<<1) + 1 <= L)
	{
		if( C[H[(i<<1)+1]]<C[H[i<<1]] ) return (i<<1)+1;
		return i<<1;
	}
	return i<<1;
}

void up(int nod)
{
	int P=poz[nod];
	
	if(C[H[P]]<C[H[P>>1]])
	{
		swap(nod,H[P>>1]);
		up(nod);
	}
}

void down(int nod)
{
	int P=poz[nod];
	
	if( (P<<1) <= L )
	{
		int k=pmin(P);
		if(C[H[P]]>C[H[k]])
		{
			swap(nod,H[k]);
			down(nod);
		}
	}
}

void push(int nod)
{
	H[++L]=nod;
	poz[nod]=L;
	up(nod);
}

void pop(int nod)
{
	int nod2=H[L];
	swap(nod,nod2);
	L--;
	down(nod2);
}

	

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	p=new lista;
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x,&y,&cst);
		
		add(x,y,cst);
		add(y,x,cst);
	}
	
	for(i=2;i<=n;i++)
	{
		T[i]=1;
		C[i]=Inf;
	}
	C[0]=-Inf;
	nod=1; N=1;
	
	while(nod)
	{
		for(p=v[nod];p;p=p->adr)
		{
			if(T[p->inf])
			{
				if(C[p->inf]==Inf) 
				{
					C[p->inf]=p->cost;
					push(p->inf);
				}
				else if(C[p->inf]>p->cost)
				{
					C[p->inf]=p->cost;
					T[p->inf]=nod;
					up(p->inf);
				}
			}
		}
		
		if(N==n) {nod=0; break;}
		else nod=H[1];
		
		Arb[nod]=T[nod];
		T[nod]=0;
		N++;
		pop(nod);
		Cost+=C[nod];
	}
	
	printf("%d\n%d\n",Cost,n-1);
	
	for(i=2;i<=n;i++)
		printf("%d %d\n",i,Arb[i]);
	
	return 0;
}