#include<fstream>
#include<iostream>
using namespace std;
long n,m,c[200001],x[200001],y[200001],i,j,aux,l[200001],mm,sol[200000],sol2[200000];
int main()
{
	ifstream f("apm.in");
	f>>n>>m;
	for(i=1;i<=m;i++)
		f>>x[i]>>y[i]>>c[i];
	for(i=1;i<=n;i++)
		l[i]=i;
	for(i=1;i<=m;i++)
		for(j=i+1;j<=m;j++)
		{
			if(c[i]>c[j])
			{
				aux=c[i];
				c[i]=c[j];
				c[j]=aux;
				aux=x[i];
				x[i]=x[j];
				x[j]=aux;
				aux=y[i];
				y[i]=y[j];
				y[j]=aux;
			}
		}
//	for(i=1;i<=m;i++)
	//		cout<<x[i]<<" "<<y[i]<<'\n';
//	cout<<'\n'<<'\n';
	i=0;	
	long long nr=0,cc=0,m2;
	while(nr<n-1)
	{
		i++;

		if(l[x[i]]!=l[y[i]])
		{
			nr++;
			u=1;
			cc+=c[i];
			sol[nr]=x[i];
			sol2[nr]=y[i];
			mm=min(x[i],y[i]);
			m2=max(x[i],y[i]);
			for(j=1;j<=n;j++)
				if(l[j]==l[mm])
					l[j]=l[m2];
		}
	}
	ofstream g("apm.out");
	g<<cc<<'\n'<<n-1<<'\n';
	for(i=1;i<n;i++)
		g<<sol[i]<<" "<<sol2[i]<<'\n';
}