#include <cstdio>

using namespace std;
int n,m,costAPM;
int A[200001],c[200001];
struct muchie {	int a,b,c;} G[400001];

void Initializare()
{
	int i;
	FILE * in=fopen("apm.in","r");
	fscanf(in,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
		fscanf(in,"%d%d%d",&G[i].a, &G[i].b, &G[i].c);
	for(i=1;i<=n;i++)
		c[i]=i;
}

void Afisare()
{
	FILE * out=fopen("apm.out","w");
	int i;
	fprintf(out,"%d\n%d\n",costAPM,n-1);
	for(i=1;i<n;i++)
		fprintf(out,"%d %d\n",G[A[i]].a,G[A[i]].b,G[A[i]].c);
}

void SortareMuchii(int st, int dr)
{
	int i,j;
	muchie x;
	if(st<dr)
	{
		x=G[st];
		i=st;
		j=dr;
		while(i<j)
		{
			while(i<j && G[j].c>=x.c)
				j--;
			G[i]=G[j];
			while(i<j && G[i].c<=x.c)
				i++;
			G[j]=G[i];
		}
		G[i]=x;
		SortareMuchii(st,i-1);
		SortareMuchii(i+1,dr);
	}
}

	
main()
{
	int i,j,min,max,nrmsel;
	Initializare();
	SortareMuchii(1,m);
	nrmsel=0;
	for(i=1; nrmsel<n-1; i++)
		if(c[G[i].a]!=c[G[i].b])
		{
			A[++nrmsel]=i;
			costAPM+=G[i].c;
			if(G[i].a<G[i].b)
			{
				min=c[G[i].a];
				max=c[G[i].b];
			}
			else
			{
				min=c[G[i].b];
				max=c[G[i].a];
			}
			for(j=1;j<=n;j++)
				if(c[j]==max)
					c[j]=min;
		}
	Afisare();
}