#include<fstream>
#include<vector>
#include<list>
#define NMAX 100005

using namespace std;


long n,m;
struct muchie
{
	long vf1;
	long vf2;
	long cost;
	muchie()
	{}
	muchie(long nvf1,long nvf2,long ncost)
	{
		cost=ncost;
		vf1=nvf1;
		vf2=nvf2;
	}
};

vector<muchie> E;
vector<muchie> MST;
long tata[NMAX],cost; 

void prelucreaza(long p,long q,long &m)
{
	long i=p-1,j;
	muchie pivot=E[m],aux;

	for(j=p;j<=q-1;j++)
		if(pivot.cost>=E[j].cost)
		{
			i++;
			aux=E[j];
			E[j]=E[i];
			E[i]=aux;
		}

	aux=E[i+1];
	E[i+1]=E[m];
	E[m]=aux;
	m=i+1;
}

void quick_sort(long p,long q)
{
	long m=q;
	if(p<q)
	{
		prelucreaza(p,q,m);
		quick_sort(p,m-1);
		quick_sort(m+1,q);
	}
}

long find(long varf)
{
	long temp=varf;
		while(tata[temp]>=0)
			temp=tata[temp];


	return temp;
}

int main()
{
	long i,x,y,c;
	fstream fin,fout;
	fin.open("apm.in",ios::in);
	fout.open("apm.out",ios::out);

	fin>>n>>m;
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>c;
		muchie a(x,y,c);
		E.push_back(a);
	}
	for(i=1;i<=n;i++)
	{
		tata[i]=-1;
	}
	quick_sort(0,m-1);

	muchie a;
	long varfUnu,varfDoi,tv1,tv2;

	for(i=0;i<m;i++)
	{
		a=E[i];
		varfUnu=a.vf1;
		varfDoi=a.vf2;
		if((tv1=find(varfUnu)) != (tv2=find(varfDoi)))
		{
			if(tv1<tv2)
				tata[varfDoi]=tv1;
			else
				tata[varfUnu]=tv2;
			cost+=a.cost;
			MST.push_back(a);
		}
	}
	
	vector<muchie>::iterator itr;

	fout<<cost<<'\n';
	fout<<MST.size()<<'\n';
	for(itr=MST.begin(); itr != MST.end(); itr++)
	{
		fout<<(*itr).vf1<<" "<<(*itr).vf2<<'\n';
	}

	fin.close();
	fout.close();
	return 0;
}