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