#include<stdio.h>
#include<malloc.h>

typedef struct 
{
	int x;
	int y;
	int cost;
} xy;

xy M[200001];
long int n;
long int m;
long int T[200001];
short int viz[400001];
long long S;
short int rang[200001];

void citire(void)
{
	FILE *f = fopen("apm.in","r");
	
	fscanf(f,"%d %d",&n,&m);
	for(int i=1;i<=m;i++)
		fscanf(f,"%d %d %d",&M[i].x,&M[i].y,&M[i].cost);
	
	fclose(f);
}

long int poz(int li,int ls)
{
	int i1 = 0;
	int j1 = -1;
	int jiaux = 0;
	xy c = M[(int)(li+ls)/2];
	M[(int)(li+ls)/2] = M[li];
	M[li] = c;
	while(li<ls)
	{
		if(M[li].cost>M[ls].cost) //|| (M[li].cost == M[ls].cost && M[li].cost*M[li].val <M[ls].cost*M[ls].val))
		{
			c = M[li];
			M[li] = M[ls];
			M[ls] = c;
			jiaux = -i1;
			i1 = - j1;
			j1 = jiaux;
		}
		li += i1;
		ls += j1;
	}
	return li;
}

void quick(int li,int ls)
{
	if(li<ls)
	{
	long int k = poz(li,ls);
	quick(li,k-1);
	quick(k+1,ls);
	}
}

int rad(int n)
{
	if(T[n] == n)
		return n;
	else
		return rad(T[n]);
}

void reuneste(int i,int j)
{
	i = rad(i);
	j = rad(j);
	if(rang[i]<rang[j])
		T[i] = j;
	else
		T[j] = i;
	if(rang[i] == rang[j])
		rang[i] ++;
}

void complet(void)
{
	for(int i=1;i<=n;i++)
		T[i] = i;
}

void kruscal(void)
{
	long int nr = 0;
	long int k = 1;
	long int pz = 0;
	complet();
	for(int i=1;k<n;i++)
	{
		if(rad(M[i].x) != rad(M[i].y))
		{
			S+=M[i].cost;
			viz[i] = 1;
			reuneste(M[i].x,M[i].y);
			k ++;
		}
	}
}

void afisare(void)
{
	FILE *f = fopen("apm.out","w");
	
	fprintf(f,"%lld\n",S);
	fprintf(f,"%d\n",n-1);
	for(int i=1;i<=m;i++)
		if(viz[i] == 1)
			fprintf(f,"%d %d\n",M[i].x,M[i].y);
	
	fclose(f);
}

int main()
{
	citire();
	quick(1,m);
	kruscal();
	afisare();
	return 0;
}