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

using namespace std;

const int Nmax1 = 200001;
const int Nmax2 = 400001;

typedef struct muchie { int x,y,cost; }MUCHIE;
MUCHIE v[Nmax2],APM[Nmax1];                     
int n,m,nr_APM,CostAPM;      // nr_APM - numarul elementelor din APM,care este la sfarsit n-1

int T[Nmax1],Rang[Nmax1];        // T[i] reprezinta tatal nodului i din arborele padurii de multimi disjuncte
                                         // Rang[i] reprezinta distanta de la varful i pana la cea mai departata frunza
FILE *in,*out;

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

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

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

int FindRoot(int x)
{
	int i,a;
	for(i = x ; T[i] != i ; i = T[i])            // la terminarea for-ului,i va fi radacina/reprezentantul arborelui/set-ului
		;
	while(T[x] != x)                     // path compresion/compresia drumurilor
	{
		a = T[x];
		T[x] = i;
		x = a;
	}
	return i;
}

void Link(int x,int y)
{
	if(Rang[x] < Rang[y])
		T[x] = y;
	else
		if(Rang[x] > Rang[y])
			T[y] = x;
		else                       // daca radacinile celor doi arbori pe care-i unesc au acelasi rang,trebuie sa maresc rangul radacinii arborelui care va fi arborele de a carui radacina se uneste celalalt arbore cu 1
		{
			T[x] = y;
			Rang[y]++;
		}
}


void Unite(int x,int y)
{
	Link(FindRoot(x),FindRoot(y));
}

void Solve()
{
	for(int i = 1 ; i <= n ; i++)
		MakeSet(i);
	sort(v+1,v+m+1,cmp);           // sortam muchiile dupa urmatorul criteriu : costul fiecarei muchii
	for(int i = 1 ; i <= m ; i++)
		if(FindRoot(v[i].x) != FindRoot(v[i].y))
		{
			nr_APM++;
			APM[nr_APM].x = v[i].x;
			APM[nr_APM].y = v[i].y;
			APM[nr_APM].cost = v[i].cost;
			CostAPM = CostAPM + v[i].cost;
			Unite(v[i].x,v[i].y);       // unesc cele doua componente conexe ale APM-ului in constructie,care contin varfurile v[i].x si v[i].y
		}
}

void 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);
	fclose(in);
	fclose(out);
}

int main()
{
	nr_APM = 0;
	CostAPM = 0;
	read();
	Solve();
	printAPM();
	return 0;
}