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

using namespace std;

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

vector<muchie> E;
vector<muchie> MST;
vector<long> tata;
long n,m;


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

	for(j=p;j<q;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)
{
	if(varf!=tata[varf])
		tata[varf]=find(tata[varf]);
	return tata[varf];
}

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;

	for(i=0;i<m;i++)
	{
		fin>>x>>y>>cost;
		E.push_back(muchie(x,y,cost));
	}

	for(i=0;i<=n;i++)
	{
		tata.push_back(i);
	}


	quick_sort(0,m-1);
	long r1,r2;
	cost=0;
	for(i=0;i<m;i++)
	{
		r1=find(E[i].vf1);
		r2=find(E[i].vf2);
		if(r1!=r2)
		{
			tata[r2]=r1;
			cost+=E[i].cost;
			MST.push_back(E[i]);
		}
	}

	fout<<cost<<'\n';
	fout<<MST.size()<<'\n';
	vector<muchie>::iterator itr;
	for(itr=MST.begin(); itr!= MST.end(); itr++)
		fout<<(*itr).vf1<<" "<<(*itr).vf2<<'\n';
	fin.close();
	fout.close();
	return 0;
}