#include<fstream>
#include<iostream>
using namespace std;
long 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]<<" "<<c[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++;
			cc+=c[i];
			sol[nr]=x[i];
			sol2[nr]=y[i];
			if(l[x[i]]>l[y[i]])
			{
				mm=l[y[i]];
				m2=l[x[i]];
			}
			else 
			{
				mm=l[x[i]];
				m2=l[y[i]];
			}
			
		//	for(j=1;j<=n;j++)	
			//	cout<<l[j]<<" ";
			//	cout<<'\n';
			for(j=1;j<=n;j++)
				if(l[j]==m2)
					l[j]=mm;
				
		//	cout<<l[m2]<<'\n';
			
		//	for(j=1;j<=n;j++)	
		//		cout<<j<<" ";
		//		cout<<'\n';
				
		//	for(j=1;j<=n;j++)	
		//		cout<<l[j]<<" ";
		//		cout<<'\n';
		//		cout<<'\n'<<'\n';
		}
	}
	ofstream g("apm.out");
	g<<cc<<'\n'<<n-1<<'\n';
	for(i=1;i<=nr;i++)
		g<<sol[i]<<" "<<sol2[i]<<'\n';
}