#include<fstream.h>
int v1[400100],v2[400100],cost[400100],h[400100],padre[200100],s[200100];
void qs(int i, int j)
{
	int s=i,d=j,aux,piv=h[(i+j)>>1];
	while(s<=d)
	{
		while(cost[h[s]]<cost[piv])
			s++;
		while(cost[h[d]]>cost[piv])
			d--;
		if(s<=d)
		{
			aux=h[d];
			h[d]=h[s];
			h[s]=aux;
			s++;
			d--;
		}
	}
	if(s<j)
		qs(s,j);
	if(i<d)
		qs(i,d);
}
int main()
{
	int su=0,n,m,x,y,c,cx,cy,q=0,i;
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	while(m--)
	{
		f>>x>>y>>c;
		v1[++q]=x;
		v2[q]=y;
		cost[q]=c;
		h[q]=q;
	}
	for(i=1;i<=n;i++)
		padre[i]=i;
	qs(1,q);
	for(i=1;i<=q&&s[0]<n-1;i++)
	{
		cx=0;
		cy=0;
		x=v1[h[i]];
		y=v2[h[i]];
		while(x!=padre[x])
		{
			x=padre[x];
			cx++;
		}
		while(y!=padre[y])
		{
			y=padre[y];
			cy++;
		}
		if(x!=y)
		{
			if(cx>cy)
				padre[v2[h[i]]]=v1[h[i]];
			else
				padre[v1[h[i]]]=v2[h[i]];
			s[++s[0]]=h[i];
			su+=cost[h[i]];
		}			
	}
	g<<su<<'\n';
	g<<n-1<<'\n';
	for(i=1;i<=n-1;i++)
		g<<v1[s[i]]<<' '<<v2[s[i]]<<'\n';
	return 0;
}