#include<stdio.h>
#include<STDLIB>
long n,m;
long t[200005];
long h[200005];
struct casy
{
	long a,b,c;
};
casy v[400004];
int cmp(casy c1,casy c2)
{
	if(c1.c==c2.c)
		return 0;
	if(c1.c>c2.c)
		return -1;
	return 1;
}
long find(long x)
{
	int i=x;
	while(i!=t[i])
	{
		i=t[i];
	}
	return i;
}
void mica_unire(long a,long b)
{
	int x,y;
	x=find(a);
	y=find(b);
	if(h[x]==h[y])
	{
		h[x]++;
		t[y]=x;
	}
	else
	{
		if(h[x]>h[y])
			t[y]=x;
		else
			t[x]=y;
	}
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	long i,c=0;
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++)
		t[i]=i;
	for(i=1;i<=m;i++)
		scanf("%ld%ld%ld",&v[i].a,&v[i].b,&v[i].c);
	qsort(v+1,v+m+1,cmp);
	for(i=1;i<=m;i++)
		if(find(v[i].a)!=find(v[i].b))
		{
			c+=v[i].c;
			mica_unire(v[i].a,v[i].b);
		}
	printf("%ld\n%ld\n",c,n-1);
	for(i=1;i<=n;i++)
	{
		t[i]=i;
		h[i]=0;
	}
	for(i=1;i<=m;i++)
		if(find(v[i].a)!=find(v[i].b))
		{
			printf("%ld %ld\n",v[i].a,v[i].b);
			mica_unire(v[i].a,v[i].b);
		}
	return 0;
}