#include<fstream>
#define M 2000000000;
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int c[20000][20000],n,m,s,viz[200001],t[200001],mini;
void citire()
{
	int x,y,C,i,j;
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				c[i][j]=0;
			else c[i][j]=M;
	while(f>>x>>y>>C)
		c[x][y]=c[y][x]=C;
}
int main()
{	int k,i,poz,nrl;
	
	citire();
	nrl=0;s=0;
	for(i=2;i<=n;i++)
		viz[i]=1;
	for(k=1;k<=n-1;k++)
	{
		mini=M;
		for(i=1;i<=n;i++)
			if(viz[i])
				if(mini>c[viz[i]][i])
			{
				poz=i;mini=c[viz[i]][i];
			}
		nrl++;
		s+=mini;
		t[poz]=viz[poz];
		for(i=1;i<=n;i++)
			if(viz[i]&&c[i][viz[i]]>c[i][poz])
				viz[i]=poz;
			viz[poz]=0;
	}
	g<<s<<"\n"<<nrl<<"\n";
	for(i=2;i<=nrl+1;i++)
		g<<i<<" "<<t[i]<<"\n";
	return 0;
}