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

	}

muchie operator =(const muchie &ob)
		{
			x=ob.x;
			y=ob.y;
			cost=ob.cost;
			return *this;
		}


	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
{
FILE * f; //fisierul de intrare
FILE * g;	//fisierul de iesire
int cost_arb;
int nrm_arb;
int N,M;
int *r;
int *h;
muchie *vm;
muchie *A;

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

	void citeste()
	{
		//f>>N>>M;
		fscanf(f,"%d%d",&N,&M);
		vm = new muchie[M];

		for(int i=0;i<M;i++)
		//f>>vm[i].x>>vm[i].y>>vm[i].cost;
			fscanf(f,"%d%d%d",&vm[i].x,&vm[i].y,&vm[i].cost);
		
		qsort(vm,M,sizeof(muchie),compare);
		
		r = new int[N+1];
		memset(r,0,sizeof(int)*(N+1));
		h = new int[N+1];
		memset(h,0,sizeof(int)*(N+1));
	}
	void MakeSet(int u)
	{
		r[u]=0;
	}

	int FiindSet(int u)
		{
			if(r[u]==0)return u;
			else
				r[u]= FiindSet(r[u]);
			return r[u];
				
		}
		
	void Union(int u,int v)
	{
		u = FiindSet(u);
		v = FiindSet(v);
		if(h[u]>h[v])r[v]=u;
		else
		r[u]=v;
		
		if(h[u]==h[v])h[v]++;
		
	}

	
	
	void K()
	{
		A = new muchie[M];
		
		//for(int i=1;i<=N;i++)
		//	MakeSet(i);
		
		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;
		fprintf(g,"%d\n%d\n",cost_arb,nrm_arb);

		for(int i=1;i<=nrm_arb;i++)
			//g<<A[i].x<<" "<<A[i].y<<endl;
			fprintf(g,"%d %d\n",A[i].x,A[i].y);

	}

	~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 apm::FiindSet(int u)
		{
			if(r[u]==0)return u;
			else
				r[u]= FiindSet(r[u]);
			return r[u];
				
		}
*/
int main()
{
apm A;
A.citeste();
A.K();	

	return 0;
}