#include <fstream>
#define INF 100000001
#define NMAX 1501

using namespace std;

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

void citire();
void initializare();
void alg_prim();
void afisare();

struct muchie
{
	int y;
	double c;
} G[NMAX][NMAX];

int Nr[NMAX], M[NMAX];
int tata[NMAX], cmin[NMAX];
int n, m, start;
int cost;

int main()
{
	citire();
	initializare();
	alg_prim();
	afisare();
	return 0;
}

void citire()
{
	int i;
	int x, y, c;
	fin>>n>>m;
	start=1;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		Nr[x]++;
		G[x][Nr[x]].y=y;
		G[x][Nr[x]].c=c;
		Nr[y]++;
		G[y][Nr[y]].y=x;
		G[y][Nr[y]].c=c;
	}
}

void initializare()
{
	int i;
	for(i=1;i<=n;i++)
	{
		cmin[i]=INF;
		tata[i]=start;
	}
	for(i=1;i<=Nr[start];i++)
		cmin[G[start][i].y]=G[start][i].c;
	tata[start]=0;
	cmin[start]=0;
	M[start]=1;
}

void alg_prim()
{
	int i, j, k;
	int mn, vf;
	for(i=1;i<=n-1;i++)
	{
		mn=INF+1;
		for(j=1;j<=n;j++)
			if(M[j]==0 && cmin[j]<mn)
			{
				mn=cmin[j];
				vf=j;
			}
		M[vf]=1;
		//fout<<vf<<' '<<tata[vf]<<'\n';
		cost+=mn;
		//actualizez costurile
		for(j=1;j<=Nr[vf];j++)
			if(M[G[vf][j].y]==0 && cmin[G[vf][j].y]>G[vf][j].c)
			{
				cmin[G[vf][j].y]=G[vf][j].c;
				tata[G[vf][j].y]=vf;
			}
	}
}


void afisare()
{
	int i;
	fout<<cost<<'\n';
	fout<<n-1<<'\n';
	for(i=2;i<=n;i++)
		fout<<i<<' '<<tata[i]<<'\n';
}