#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct arbore
{
	int x,y,c;
};
arbore a[500001];
int compara(arbore a, arbore b)
{
	return a.c<b.c;
}
int n,m,i,j,costm=0;
int b[500001],d[500001];
int nr=0;
int det(int x)
{
	int r;
	int y;
	r=x;
	while(r!=d[r])
		r=d[r];
	while(x!=d[x])
	{
		y=d[x];
		d[x]=r;
		x=y;
	}
	return r;
}
void calculeaza()
{
	int m1,m2,i;
	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()
{
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>a[i].x>>a[i].y>>a[i].c;
	for(i=1;i<=n;i++)
		d[i]=i;
	sort(a+1,a+m+1,compara);
	calculeaza();
	g<<costm<<"\n";
	g<<nr;
	for(i=1;i<=nr;i++)
		g<<a[b[i]].y<<" "<<a[b[i]].x<<"\n";
	return 0;
}