//Kruskal pentru BC

#include <stdio.h>
#define lg_max 400010

int n,m;
int tata[lg_max],niv[lg_max];

struct nod
{
	int x,y,cost;
} sir[lg_max];

void citire()
{
	scanf ("%d %d",&n,&m);
	for (int i=0;i<m;i++)
		scanf ("%d %d %d",&sir[i].x,&sir[i].y,&sir[i].cost);
}


void sortare(int st,int dr)
{
	int i=st,j=dr;
	int pivot=sir[(st+dr)>>1].cost;
	nod aux;
	while (i<=j)
	{
		while (sir[i].cost<pivot)
			i++;
		while (sir[j].cost>pivot)
			j--;
		if (i<=j)
		{
			aux=sir[i];
			sir[i]=sir[j];
			sir[j]=aux;
			i++;
			j--;
		}
	}
	if (i<dr)
	    sortare(i,dr);
	if (j>st)
		sortare(st,j);
}

int tati(int nod)
{
	int aux=nod;
	while (tata[nod]!=nod)
		nod=tata[nod];

	while (tata[aux]!=aux)
	{
	     aux=tata[aux];
	     tata[aux]=nod;
	}
	return nod;
}

void reuniune(int nod1,int nod2)
{
	int T1=tati(nod1);
	int T2=tati(nod2);
	if (T1==T2)
		return ;
	if (niv[T1]<niv[T2])
	{
		tata[T2]=T1;
		niv[T1]++;
	}
	else
	{
		tata[T1]=T2;
		niv[T2]++;
	}
}

void alg()
{
	int rez[lg_max],num=0,S=0,i;

	sortare(0,m-1);
	for (i=0;i<=m;i++)
		tata[i]=i;

	for (i=0;i<m;i++)
	{
		if (tata[sir[i].x] != tata[sir[i].y])
		{
			S+=sir[i].cost;
			rez[num++]=i;
			reuniune(sir[i].x , sir[i].y);
		}
	}
//afisare

	printf("%d\n",S);
	printf("%d\n",num);
	for (i=0;i<num;i++)
		printf("%d %d\n",sir[rez[i]].x,sir[rez[i]].y);
}

int main ()
{
	freopen ("apm.in","r",stdin);
	freopen ("apm.out","w",stdout);
	citire();
	alg();
	return 0;
}