#include<iostream>
using namespace std;
#include<fstream>
#include<stdlib.h>
class muchie
{
unsigned int x,y;
short int cost;
public:
	friend class apm;
	friend int compare(const void *x1,const void *x2); 
	muchie()
	{
		x=y=cost=0;

	}



	muchie(const muchie &ob)
	{
		x=ob.x;	y=ob.y;	cost=ob.cost;
	}

bool operator<(const muchie &ob)
	{
		return cost<ob.cost;
	}
bool operator>(const muchie &ob)
	{
		return cost>ob.cost;
	}

bool operator<=(const muchie &ob)
	{
		return cost<=ob.cost;
	}

bool operator>=(const muchie &ob)
	{
		return cost>=ob.cost;
	}

};
int compare(const void *x1,const void *x2)
	{
		muchie *m1 = (muchie *)x1;
		muchie *m2 = (muchie *)x2;
		return (*m1).cost-(*m2).cost;
	}

class apm
{
ifstream f; //fisierul de intrare
ofstream g;	//fisierul de iesire
int cost_arb;
int nrm_arb;
int N,M;
int *r;
muchie *vm;
muchie *A;

public:
	apm()
	{
		f.open("apm.in");
		g.open("apm.out");
		vm=NULL;	A=NULL;	cost_arb=0;	nrm_arb=0;
	}

	void citeste()
	{
		f>>N>>M;
		vm = new muchie[M];

		for(int i=0;i<M;i++)
		f>>vm[i].x>>vm[i].y>>vm[i].cost;
		
		qsort(vm,M,sizeof(muchie),compare);

		r = new int[N+1];
		for(int i=1;i<=N;i++) //MakeSet;
			r[i]=i;
	}

	int FiindSet(int u)
		{
			return r[u];
		}

	void Union(int u,int v)
	{
		for(int i=1;i<=N;i++)
			if(r[i]==r[u])r[i]=r[v];
	}

	void K()
	{
		A = new muchie[M];
		
		for(int i=0;i<M;i++)
		{	if(FiindSet(vm[i].x)!=FiindSet(vm[i].y))
			{
				A[++nrm_arb]=vm[i];
				cost_arb+=A[nrm_arb].cost;
				Union(vm[i].x,vm[i].y);
			}
			if(nrm_arb==N-1)break;
		}
	g<<cost_arb<<endl<<nrm_arb<<endl;

		for(int i=1;i<=nrm_arb;i++)
			g<<A[i].x<<" "<<A[i].y<<endl;

	}

	~apm()
	{
	//	for(int i=0;i<M;i++)
		//	cout<<vm[i].x<<" "<<vm[i].y<<" "<<vm[i].cost<<endl;
		delete []vm;
		delete []r;
		delete []A;
	}
};

int main()
{
apm A;
A.citeste();
A.K();	

	return 0;
}