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