#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef struct muchie { int x,y,cost; }MUCHIE;

class GrafNeorientat
{
protected:
	MUCHIE v[400001];
	int n,m;
	FILE *in,*out;
public:
	GrafNeorientat();
	~GrafNeorientat();
};

GrafNeorientat::GrafNeorientat()
{
	in=fopen("apm.in","r");
	out=fopen("apm.out","w");
	fscanf(in,"%d %d",&n,&m); cout<<m;
	for(int i = 1 ; i <= m ; i++)
		fscanf(in,"%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
}

GrafNeorientat::~GrafNeorientat()
{
	fclose(in);
	fclose(out);
}

class Kruskal : public GrafNeorientat
{
	int* T;
	int* Rang;
	MUCHIE APM[400001];
	int CostAPM,nr_APM;
public:
	Kruskal();            // constructor
	~Kruskal();
	void MakeSet(int);
	int FindRoot(int);
	void Link(int,int);
	void Unite(int,int);
	void Solve();
	void printAPM();
};

Kruskal::Kruskal()
{  
	T = new int[200001];
	Rang = new int[200001];
	CostAPM = 0;
	nr_APM = 0;
	for(int i = 1 ; i <= n ; i++ )
		this->MakeSet(i);
}

Kruskal::~Kruskal()
{
	delete [] T;
	delete [] Rang;
}

bool cmp(MUCHIE x,MUCHIE y)
{
	return (x.cost < y.cost);
}

inline void Kruskal::MakeSet(int x)
{
	T[x] = x;
	Rang[x] = 1;
}

int Kruskal::FindRoot(int x)
{
	int i,a;
	for( i = x ; T[i] != i ; i = T[i] )        // cand se termina for-ul,i o sa fie radacina/reprezentantul arborelui/set-ului din care face parte x
		;
	while(T[x] != x)                // facem path compresion/compresia drumurilor
	{
		a = T[x];
		T[x] = i;
		x = a;
	}
	return i;
}

inline void Kruskal::Link(int x,int y)
{
	if(Rang[x] < Rang[y])
		T[x] = y;
	else
		if(Rang[x] > Rang[y])
			T[y] = x;
		else
			if(Rang[x] == Rang[y])
			{
				T[x] = y;
				Rang[y]++;
			}
}

void Kruskal::Unite(int x,int y)
{
	this->Link(FindRoot(x),FindRoot(y));
}

void Kruskal::Solve()
{
	int i,a,b,CapatMuchie1,CapatMuchie2,CostMuchie;     // CapatMuchie1 - primul varf al muchiei,CapatMuchie2 - al doilea varf al muchiei
	sort(v + 1,v + m + 1,cmp);
	for(i = 1 ; i <= m ; i++ )
	{	
		CapatMuchie1 = v[i].x;
		CapatMuchie2 = v[i].y;
		CostMuchie = v[i].cost;
		a = this->FindRoot(CapatMuchie1);
		b = this->FindRoot(CapatMuchie2);
		if( a != b )
		{
			nr_APM++;
			APM[nr_APM].x = CapatMuchie1;
			APM[nr_APM].y = CapatMuchie2;
			APM[nr_APM].cost = CostMuchie;                                  // se poate renunta la memorarea costului muchiilor din APM
			CostAPM = CostAPM + CostMuchie;
			this->Unite(CapatMuchie1,CapatMuchie2);                    // merge si cu a,b , e mai rapid
		}
	}
}

inline void Kruskal::printAPM()
{
	fprintf(out,"%d\n%d\n",CostAPM,n-1);
	for(int i = 1 ; i <= n-1 ; i++)
		fprintf(out,"%d %d\n",APM[i].x,APM[i].y);
}

int main()
{
	Kruskal G;
	G.Solve();
	G.printAPM();
	return 0;
}