#include<iostream>
#include<fstream>
using namespace std;
struct element
{
	long x,y,c;
};
int main()
{
	long i,j,m,n,l[100],cost=0,k,p=0;
	element v[100],aux,b[100];
	fstream f("apm.in",ios::in);
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>v[i].x>>v[i].y>>v[i].c;
	}
	f.close();
	for(i=1;i<m;i++)
	{
		for(j=i+1;j<=m;j++)
		{
			if(v[i].c>v[j].c)
			{
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		l[i]=i;
	}
	for(i=1;i<=m;i++)
	{
		if(l[v[i].x]!=l[v[i].y])
		{
			cost=cost+v[i].c;
			k=l[v[i].x];
			for(j=1;j<=n;j++)
			{
				if(l[j]==k)
				{
					l[j]=l[v[i].y];
				}
			}
			p++;
			b[p].x=v[i].x;
			b[p].y=v[i].y;
			
		}
	}
	fstream g("apm.out",ios::out);
	g<<cost<<endl;
	g<<p<<endl;
	for(i=1;i<=p;i++)
	{
		g<<b[i].y<<" "<<b[i].x<<endl;
	}
	g.close();
}