#include <fstream>
#define InFile "apm.in"
#define OutFile "apm.out"
#define NMAX 200000
#define MMAX 400000
using namespace std;

ofstream fout(OutFile);
int C[NMAX],n,m,much,cost;
struct arc{int x,y,c;} M[MMAX],aux,B[NMAX];
int tata[NMAX],h[NMAX];
void citire();
void Union (int,int);
int find(int);
void afisare();
int Divide (int st, int dr) 
	{
	int i=st, j=dr, di=0, dj=1;
	while(i < j)
	{ 
		if(M[i].c > M[j].c)
		{ 
			aux=M[i];
			M[i]=M[j];
			M[j]=aux;
			di=1-di;
			dj=1-dj; 
		}
		i+=di;
		j-=dj; 
	}
	return i;
	}
void QSort(int st, int dr)
{
	int poz;
	if (st<dr) 
		{
			poz=Divide(st,dr);
			QSort(st,poz-1);
			QSort(poz+1,dr);
		}
}
int main()
{
	citire();
	QSort(0,m-1);
	int a,b;
	while (much<n-1)
	{
	for (int i=0;i<m;i++)
		{
			a=find(M[i].x);
			b=find(M[i].y);
			if (a!=b)
				{
					cost+=M[i].c;
					B[much]=M[i];
					much++;
					Union(a,b);
				}
		}
	}
	afisare();
	return 0;
}

void citire()
{
	ifstream fin(InFile);
	fin>>n>>m;
	for (int i=0;i<m;i++)
		fin>>M[i].x>>M[i].y>>M[i].c;
}

void Union(int rad1, int rad2)
{
	if (h[rad1]<h[rad2])
		tata[rad1]=rad2;
	else
		{
			tata[rad2]=rad1;
			if (h[rad1]==h[rad2]) h[rad1]++;
		}	
}

int find(int x)
{
	while (tata[x])
		x=tata[x];
	return x;
}

void afisare()
{
	fout<<cost<<'\n'<<n-1<<"\n";
	for (int i=0;i<n-1;i++)
		{
			fout<<B[i].x<<" "<<B[i].y<<"\n";
		}
}