#include <stdio.h>
#define nmax 200001
#define mmax 400001
long n,m;
long cnt=0;
long t[nmax],h[nmax],cost=0;
struct muchie
{
	long x,y;
	int c;
};
muchie v[mmax],m1[mmax],m2[mmax],sol[nmax];
void citire(void)
{
	FILE *fin=fopen("apm.in","r");
	fscanf(fin,"%ld %ld",&n,&m);
	for (long i=1;i<=m;i++)
		fscanf(fin,"%ld %ld %ld",&v[i].x,&v[i].y,&v[i].c);
	fclose(fin);
}
void merge(long ls,long ld)
{
	if (ls<ld)
	{
		long mij=(ls+ld)/2;
		merge(ls,mij);
		merge(mij+1,ld);
		long i1=0,i2=0,n1=0,n2=0,i;

		for (i1=ls;i1<=mij;i1++)
			m1[++n1]=v[i1];
		for (i2=mij+1;i2<=ld;i2++)
			m2[++n2]=v[i2];

		i1=1; i2=1;

		long k=ls-1;
		while (i1<=n1 && i2<=n2)
			if (m1[i1].c<m2[i2].c)
				v[++k]=m1[i1++];
			else
				v[++k]=m2[i2++];

		while (i1<=n1)
			v[++k]=m1[i1++];
		while (i2<=n2)
			v[++k]=m2[i2++];		
	}
}
long tata(int x)
{
	if (t[x]==x) return x;
	return tata(t[x]);
}
void solve(void)
{
	merge(1,m);
	long i;
	for (i=1;i<=n;i++)
	{
		t[i]=i;
		h[i]=1;
	}	
	i=1;
	long t1,t2;
	while(cnt!=n-1)
	{
		t1=tata(v[i].x);
		t2=tata(v[i].y);
		if (t1!=t2)
		{
			if (h[t1]<h[t2])
			{
				t[t1]=t2;
				if (h[t1]+1>h[t2]) h[t2]=h[t1]+1;
			}
			else
			if (h[t2]<=h[t1])
			{
				t[t2]=t1;
				if (h[t2]+1>h[t1]) h[t1]=h[t2]+1;
			}
			sol[++cnt]=v[i];
			cost+=v[i].c;
		}
		i++;
	}	
}
void afisare(void)
{
	FILE *fout=fopen("apm.out","w");
	fprintf(fout,"%ld\n",cost);
	fprintf(fout,"%ld\n",n-1);
	for (int i=1;i<=cnt;i++)
		fprintf(fout,"%ld %ld\n",v[i].x,v[i].y);
	fclose(fout);
}
int main()
{
	citire();
	solve();
	afisare();
	return 0;
}