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