#include<fstream>
using namespace std;

struct arb
{
	int x,y,c;
};
arb a[400001];
int i,n,m,b[200001],c[200001],d[400001],cost=0,nrc;
int cmp(arb a,arb b)
{
	return a.c<b.c;
}
int rad(int q)
{
	int r=q,z;
	while(b[r]!=r)
		r=b[r];
	while(b[q]!=q)
	{
		z=b[q];
		b[q]=r;
		q=z;
	}
	return r;
}
void unite(int p,int q)
{
	nrc--;
	if(c[rad(p)]>c[rad(q)])
		b[rad(q)]=p;
	else
		b[rad(p)]=q;
	if(c[rad(p)]==c[rad(q)])
		c[rad(q)]++;
}
int main()
{
	FILE *f=fopen("apm.in","r");
	FILE *g=fopen("apm.out","w");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++)
		fscanf(f,"%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	for(i=1;i<=n;i++)
		b[i]=i,c[i]=1;
	sort(a+1,a+m+1,cmp);
	nrc=n;
	i=1;
	while(nrc>1)
	{
		while(rad(a[i].x)==rad(a[i].y))
			i++;
		unite(a[i].x,a[i].y);
		d[++d[0]]=i;
		cost+=a[i].c;
		i++;
	}
	fprintf(g,"%d\n%d\n",cost,d[0]);
	for(i=1;i<=d[0];i++)
		fprintf(g,"%d %d\n",a[d[i]].x,a[d[i]].y);
	return 0;
}