#include<fstream.h>

ofstream fout("apm.out");

int n,m,a[180][180],e,u,q[180],c[180],t[180],p=1;

void citire()
{       int x,y,z;
	ifstream fin("apm.in");
	fin>>n>>m;
	for(int i=1;i<=m;i++)
	{	fin>>x>>y>>z;
		a[x][y]=z;
		a[y][x]=z;
	}
	fin.close();
}

int vf()
{	int min=32000,x;
	for(int i=1;i<=n;i++)
		if(q[i]==1) for(int j=1;j<=n;j++)
				if(q[j]==0) if(a[i][j]<min&&a[i][j]!=0){ min=a[i][j];
									 x=i;
									}
	q[x]=0;
	p++;
	return x;
}

int main()
{       int i;
	citire();
	for(i=2;i<=n;i++)
	{	q[i]=1;
		c[i]=32000;
	}
	c[1]=0;
	t[1]=-1;
	while(p<=n)
	{	if(p>1)	u=vf();
		else{ u=1;
		      p++;
		    }
		for(i=1;i<=n;i++)
			if(q[i]==1&&a[u][i]<c[i]&&a[u][i]!=0)
			{	t[i]=u;
				c[i]=a[u][i];
			}
	}
	for(i=1;i<=n;i++)
	      if(t[i]==0) e+=a[1][i];
	      else if(t[i]>0) e+=a[i][t[i]];
	fout<<e<<"\n"<<n-1<<"\n";
	for(i=1;i<=n;i++)
		if(t[i]==0) fout<<1<<" "<<i<<"\n";
			else if(t[i]>0) fout<<i<<" "<<t[i]<<"\n";
	fout.close();
	return 0;
}