// 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 interclasare(int p,int s,int q)
{
	int i=p,j=s+1,k=0;
	while(i<=s && j<=q)
		if(g[i].c<g[j].c)
			h[++k]=g[i++];
		else
			h[++k]=g[j++];
	while (i<=s)
		h[++k]=g[i++];
	while(j<=q)
		h[++k]=g[j++];
	for(i=p;i<=q;i++)
		g[i]=h[i-p+1];

}

void sortare(int p,int q)
{
	if(p<q)
	{
		int s=(p+q)/2;
		sortare(p,s);
		sortare(s+1,q);
		interclasare(p,s,q);
	}
}

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++;
			if(con[g[i].e1]>=con[g[i].e2])
			{
				min=con[g[i].e2];
				max=con[g[i].e1];
			}
			else
				min=con[g[i].e1],max=con[g[i].e2];
			for(int i=1;i<=n;i++)
				if(con[i]==min)
					con[i]=max;
		}
	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;
}