#include<stdio.h>
#define nmax 200005
#define mmax 400005
long v[nmax],n,m,cs,w;

struct muchii
{
	long i,j,c;
};

muchii x[mmax],sol[nmax];

struct nod
{
	long info;
	nod *urm;
};

nod *t[nmax];

void read()
{
	scanf("%ld%ld",&n,&m);
	long i;
	for (i=1;i<=m;i++)
	{
		scanf("%ld%ld%ld",&x[i].i,&x[i].j,&x[i].c);
	}
}

long part(long st,long dr)
{
	long p,i,j;
	muchii aux;
	i=st-1;
	j=dr+1;
	p=x[(st+dr)/2].c;
	while (1)
	{
		do {i++;} while (x[i].c<p);
		do {j--;} while (x[j].c>p);
		if (i<j)
		{
			aux=x[i];
			x[i]=x[j];
			x[j]=aux;
		}
		else return j;
	}
	
}

void quicks(long st,long dr)
{
	long p;
	if (st<dr)
	{
		p=part(st,dr);
		quicks(st,p);
		quicks(p+1,dr);
	}
}

void init()
{
	long i;
	nod *p;
	for (i=1;i<=n;i++)
	{
		v[i]=i;
		p=new nod;
		p->info=i;
		p->urm=t[i];
		t[i]=p;
	}
}

void connect(long a,long b)
{
	nod *aux,*p;
	long r,s;
	r=v[a];
	s=v[b];
	p=t[s];
	while (p)
	{
		aux=p;
		t[s]=p->urm;
		p=t[s];
		v[aux->info]=r;
		aux->urm=t[r];
		t[r]=aux;
	}
}
	
void rez()
{
	long k=n-1,i;
	for (i=1;i<=m;i++)
	{
		if (v[x[i].i]!=v[x[i].j])
		{
			cs+=x[i].c;
			if (v[x[i].i]<v[x[i].j])
				connect(x[i].i,x[i].j);
			else connect(x[i].j,x[i].i);
			sol[++w]=x[i];
			k--;
		}
	}
}

void print()
{
	printf("%ld\n",cs);
	printf("%ld\n",w);
	long i;
	for (i=1;i<=w;i++)
	{
		printf("%ld %ld\n",sol[i].i,sol[i].j);
	}
}


int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	read();
	init();
	quicks(1,m);
	rez();
	print();
	return 0;
}