#include<fstream>
#include<algorithm>
using namespace std;

int i,j,n,m,d[200001],b[200001],costm,nr=0;
struct arb
{
	int x,y,c;
};
arb a[400001];
int cmp(arb a,arb b)
{
	return a.c<b.c;
}
int det(int x)
{
	int r,y;
	r=x;
	while(d[r]!=r)
		r=d[r];
	while(d[x]!=x)
	{
		y=d[x];
		d[x]=r;
		x=y;
	}
	return r;
}
void rezolva()
{
	int i,m1,m2;
	for(i=1;i<=m&&nr<n-1;i++)
	{
		m1=det(a[i].x);
		m2=det(a[i].y);
		if(m1!=m2)
		{
			costm+=a[i].c;
			b[++nr]=i;
			d[m1]=m2;
		}
	}
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	for(i=1;i<=n;i++)
		d[i]=i;
	sort(a+1,a+m+1,cmp);
	rezolva();
	printf("%d\n%d\n",costm,nr);
	for(i=1;i<=nr;i++)
		printf("%d %d\n",a[b[i]].x,a[b[i]].y);
	return 0;;
}