#include <fstream>
#define MMAX 400005
#define NMAX 200005

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct muchie
{
	int x, y, c;
}G[MMAX];

void citire();
void Kruskal();
int Find(int x);
void Union(int i, int j);
void extragere_Min(int &m);
void comb_heap(int rad, int m);

int n, m;
int tata[NMAX], h[NMAX], sol[NMAX];
int costmin;

int main()
{
	citire();
	Kruskal();
	return 0;
}

void citire()
{
	int i, rad;
	fin>>n>>m;
	for(i=1;i<=m;i++)
		fin>>G[i].x>>G[i].y>>G[i].c;
	for(rad=m/2;rad>0;rad--)
		comb_heap(rad, m);
}

void Kruskal()
{
	muchie x;
	int nr=0, c1, c2, y=0, i;
	while(nr<n-1)
	{
		x=G[1];
		extragere_Min(m);
		c1=Find(x.x);
		c2=Find(x.y);
		if(c1!=c2)
		{
			Union(c1, c2);
			costmin+=x.c; nr++;
			y++; sol[y]=x.x;
			y++; sol[y]=x.y;
		}
	}
	fout<<costmin<<'\n';
	fout<<y<<'\n';
	for(i=1;i<=y;i+=2)
		fout<<sol[i+1]<<' '<<sol[i]<<'\n';
	fout.close();
}

int Find(int x)
{
	int r, aux;
	r=x;
	while(tata[r]!=0) r=tata[r];
	while(tata[x]!=0)
	{
		aux=x; x=tata[x]; tata[aux]=r;
	}
	return r;
}

void Union(int i, int j)
{
	if(h[i]<h[j])
		tata[i]=j;
	else
		if(h[i]>h[j])
			tata[j]=i;
		else
			tata[i]=j, h[j]++;
}

void extragere_Min(int &m)
{
	G[1]=G[m]; m--;
	comb_heap(1, m);
}

void comb_heap(int rad, int m)
{
	muchie x=G[rad];
	int tata=rad, fiu=2*rad;
	while(fiu<=m)
	{
		if(fiu+1<=m && G[fiu].c>G[fiu+1].c) fiu++;
		//acum fiu indica pe cel mai mare dintre fii
		if(x.c>G[fiu].c)
		{
			G[tata]=G[fiu]; tata=fiu; fiu=2*tata;
		}
		else
			break;
	}
	G[tata]=x;
}