// apm.cpp : Defines the entry point for the console application.
//

#include <cstdio>
int n,m;
struct graf
{
	int e1,e2,c;
};
graf g[400001];
graf h[400001];
int con[200001];
int d[400001];
long long cost=0;
int muchii=1;


void citire()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d %d %d",&g[i].e1,&g[i].e2,&g[i].c);
	for(int i=1;i<=n;i++)
		con[i]=i;
}



void sortare(int st,int dr)
{
	int i,j;
	graf 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;
		sortare(st,i-1);
		sortare(i+1,dr);
	}

}

void lucru()
{
	int min,max;
	for(int i=1;i<=m;i++)
		if(con[g[i].e1]!=con[g[i].e2])
		{
			d[muchii]=i;
			cost=cost+g[i].c;
			muchii++;
			min=con[g[i].e1];
			for(int j=1;j<=n;j++)
				if(con[j]==min)
					con[j]=con[g[i].e2];
		}
	muchii--;
}

void scriere()
{
	printf("%lld\n",cost);
	printf("%d\n",muchii);
	for(int i=1;i<=muchii;i++)
		printf("%d %d\n",g[d[i]].e1,g[d[i]].e2);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	sortare(1,m);
	lucru();
	scriere();


	return 0;
}