#include<stdio.h>
using namespace std;
FILE *f,*g;
int t[200002],h[200002];
struct muchie
{
	int x,y,c;
};
muchie v[400002];

int sel(muchie a[],int i,int j)
{
	int di,dj;
	muchie aux;
	di=1; dj=0;
	while(i<j)
	{
		if(a[i].c > a[j].c)
		{
			aux=a[i];
			a[i]=a[j];
			a[j]=aux;
			
			di=1-di;
			dj=1-dj;
		}
		i+=di;
		j-=dj;
	}
	return i;
}

void qs(muchie a[],int l, int h)
{
	int m;
	if(l<h)
	{
		m=sel(a,l,h);
		qs(a,1,m-1);
		qs(a,m+1,h);
	}
}

int cauta(int x)
{
	int i,j;
	for(i=x;t[i]!=0;i=t[i]);
	
	for(j=x;t[j]!=0;j=t[j])
		t[j]=i;
	return i;
}

void unesc(int x,int y)
{
	if(h[x]>h[y])
		t[y]=x;
	else
		t[x]=y;
	if(h[x]==h[y])
		++h[y];
}

int main()
{
	int i,j,s,n,m,nr[400002];
	f=fopen("apm.in","rt");
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=m;++i)
		fscanf(f,"%d %d %d",&v[i].x,&v[i].y,&v[i].c);
	fclose(f);
	qs(v,1,m);
	/*for(i=1;i<=n;i++)
		h[i]=1;*/
	t[v[1].y]=v[1].x;
	h[v[1].x]++;
	s=v[1].c;
	nr[1]=1;
	j=1;
	for(i=2;i<=m;++i)
		if(cauta(v[i].x)!=cauta(v[i].y))
		{
			unesc(cauta(v[i].x),cauta(v[i].y));
			s+=v[i].c;
			++j;
			nr[j]=i;
		}
	g=fopen("apm.out","wt");
	fprintf(g,"%d\n%d\n",s,n-1);
	for(i=1;i<=j;++i)
		fprintf(g,"%d %d\n",v[nr[i]].x,v[nr[i]].y);
	fclose(g);
	return 0;
}