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

using namespace std;
int cost[400001];
class GrafOrientat
{
protected:
	int e1[400001],e2[400001];//,cost[410];              // muchia i va fi de fapt muchia v1[i] - v2[i],avand costul cost[i]
	int n,m;
	FILE *in,*out;
public:
	GrafOrientat();
	~GrafOrientat();
};

GrafOrientat::GrafOrientat()
{
	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",&e1[i],&e2[i],&cost[i]);
}

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

class Kruskal : public GrafOrientat
{
	int T[200001],Rang[200001];
	typedef struct muchie { int x,y,cost; }MUCHIE;
	MUCHIE APM[400001];
	int CostAPM,nr_APM,indice[400001];
public:
	Kruskal();            // constructor
	~Kruskal();
	//bool cmp(int,int);
	void MakeSet(int);
	int FindRoot(int);
	void Link(int,int);
	void Unite(int,int);
	void Solve();
	void printAPM();
};

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

Kruskal::~Kruskal()
{}

bool cmp(int x,int y)
{
	return (cost[x] < cost[y]);
}

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;
}

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]++;
			}
}

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

void Kruskal::Solve()
{
	int i,a,b,CapatMuchie1,CapatMuchie2,CostMuchie;     // CapatMuchie1 - primul varf al muchiei,CapatMuchie2 - al doilea varf al muchiei
	sort(indice + 1,indice + m + 1,cmp);
	for(i = 1 ; i <= m - 1 ; i++ )
	{	
		CapatMuchie1 = e1[indice[i]];
		CapatMuchie2 = e2[indice[i]];
		CostMuchie = cost[indice[i]];
		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
		}
	}
}

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;
}