#include<fstream>
using namespace std;//prim
struct muchie{int x,y,c;}u[400003];
int ind[400003],n,m,i,j,cost,sol[400003][2],k;
short viz[400003];
bool cond(int i,int j)
{
	return (u[i].c<u[j].c);
}

int main()
{
	ifstream f("apm.in");ofstream g("apm.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>u[i].x>>u[i].y>>u[i].c;
		ind[i]=i;
	}
	sort(ind+1,ind+m+1,cond);
	viz[ u[ind[1]].x ] = viz[ u[ind[1]].y ] = 1;
	cost+=u[ind[1]].c;
	k=1;
	sol[k][0]=u[ind[1]].x;
	sol[k][1]=u[ind[1]].y;
	for(i=1;i<n-1;i++)
	{
		j=1;
		while( viz[ u[ind[j]].x ] == viz[ u[ind[j]].y ] )j++;
		if(viz[ u[ind[j]].x ]==1) viz[u[ind[j]].y]=1;
		              else viz[u[ind[j]].x]=1;  
		sol[++k][0]=u[ind[j]].x;//solutia pe muchii
		sol[k][1]=u[ind[j]].y;
		cost+=u[ind[j]].c;
	}
	g<<cost<<"\n"<<n-1<<"\n";
	for(i=1;i<=k;i++)
		g<<sol[i][0]<<" "<<sol[i][1]<<"\n";
	f.close();g.close();
return 0;}