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

using namespace std;

long n,m,vizitat[NMAX],nrTotalVf,vizitat_muchii[2*NMAX];

struct muchie
{
	long vf1,vf2,cost,loc;
	muchie(){}
	muchie(long nvf1,long nvf2,long ncost,long nloc) : vf1(nvf1),vf2(nvf2),cost(ncost),loc(nloc)
	{
	}
	//muchie(muchie&);
	//muchie(muchie& nx)
	//{
	//	vf1=nx.vf1;
	//	vf2=nx.vf2;
	//	cost=nx.cost;
	//}
};

long dimH;
muchie A[NMAX];
vector<list<muchie> > V;
vector<muchie> MST;

void adauga_in_heap(muchie x)
{
	long poz1,poz2;
	muchie aux;

	A[++dimH]=x;
	poz1=dimH/2;
	poz2=dimH;
	while(A[poz1].cost>A[poz2].cost && poz1>=1)
	{
		aux=A[poz1];
		A[poz1]=A[poz2];
		A[poz2]=aux;
		poz1/=2;
		poz2/=2;
	}

}

long pozMinVf(long pz1,long pz2)
{
	if(A[pz1].cost>A[pz2].cost)
		return pz2;
	return pz1;
}

muchie minim()
{
	muchie mica=A[1],aux;
	long poz1,poz2;
	A[1]=A[dimH];
	dimH--;
	poz1=1;
	poz2=pozMinVf(poz1*2,poz1*2+1);
	while(A[poz1].cost>A[poz2].cost &&poz2<=dimH)
	{
		aux=A[poz1];
		A[poz1]=A[poz2];
		A[poz2]=aux;
		poz1*=2;
		poz2=pozMinVf(poz1*2,poz1*2+1);
	}
	

	return mica;
}

long da_varf(muchie mn)
{
	if(vizitat[mn.vf1]==0)
		return mn.vf1;
	return mn.vf2;
}
int main()
{
	long x,y,cost,i;
	fstream fin,fout;
	fin.open("apm.in",ios::in);
	fout.open("apm.out",ios::out);


	fin>>n>>m;
	nrTotalVf=n;
	list<muchie> lst;
	for(i=0;i<=n;i++)
		V.push_back(lst);
	for(i=0;i<m;i++)
	{
		fin>>x>>y>>cost;
		//adauga_in_heap(muchie(x,y,cost));
		V[x].push_back(muchie(x,y,cost,i));
		V[y].push_back(muchie(x,y,cost,i));
	}

	long varf_curent=1;
	list<muchie>::iterator itr;
	muchie mn;
	vizitat[1]=1;
	nrTotalVf--;
	cost=0;
	while(nrTotalVf!=0)
	{
		for(itr=V[varf_curent].begin(); itr!=V[varf_curent].end(); itr++)
		{
			if(vizitat_muchii[(*itr).loc]==0)
			{
				adauga_in_heap(*itr);
				vizitat_muchii[(*itr).loc]=1;
			}
		}
		mn=minim();
		while(vizitat[mn.vf2]==1 && vizitat[mn.vf1]==1)
		{
			mn=minim();
		}

		varf_curent=da_varf(mn);
		vizitat[varf_curent]=1;
		nrTotalVf--;
		MST.push_back(mn);
		cost+=mn.cost;
	}

	vector<muchie>::iterator itrv;

	fout<<cost<<'\n';
	fout<<MST.size()<<'\n';
	for(itrv=MST.begin(); itrv!=MST.end(); itrv++)
		fout<<(*itrv).vf1<<" "<<(*itrv).vf2<<'\n';
	
	fin.close();
	fout.close();
	return 0;
}