#include<stdio.h>
#include<stdlib.h>
long n,m;
long t[200005];
long h[200005];
struct casy
{
	long a,b,c;
};
casy v[400004];
int cmp(const void *a1,const void *a2)
{
	casy *c1;
	casy *c2;
	c1=(casy *)a1;
	c2=(casy *)a2;
	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,m,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;
}