#include<stdio.h>
#define N 200000
#define M 400000
#define INF 1000000000
int n,m,d[N],pred[N],costuri=0,*a[N],*b[N],*c[N],x[M],y[M],cost[M],viz[N]={0},s[N],t[N];

void citire()
{
	int i;  
    scanf("%d%d",&n,&m);  
	for(i=1;i<=m;i++)  
	{  
        scanf("%d%d%d",&x[i],&y[i],&cost[i]);  
        ++d[x[i]]; 
		++d[y[i]];
    }  
    for(i=1;i<=n;i++)  
    {  
        a[i]=new int[d[i]+1];  
		//b[i]=new int[d[i]+1];
        c[i]=new int[d[i]+1];  
        a[i][0]=0;  
		c[i][0]=0;  
	}  
	for(i=1;i<=m;++i)  
	{  
        a[x[i]][++a[x[i]][0]]=y[i];
		a[y[i]][++a[y[i]][0]]=x[i];
        c[x[i]][++c[x[i]][0]]=cost[i];
		c[y[i]][++c[y[i]][0]]=cost[i];
	}  
 }
/*
void afisareproba()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=a[i][0];j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
}
*/	
int minim()
{
	int min=1000000000,pmin;
	for(int i=1;i<=n;i++)
		if((viz[i]==0)&&(d[i]<min))
		{
			min=d[i];
			pmin=i;
		}
	return pmin;
}
void prim(int x)
{
	int y,z,xx;
	for(int i=1;i<=n;i++)
	{
		d[i]=INF;
		pred[i]=0;
	}
	d[x]=0;
	for(int i=1;i<=n;i++)
	{
		y=minim();
		viz[y]=1;
		if(x!=y)
		{
			s[i-1]=y;
			t[i-1]=pred[y];
		}
		costuri+=d[y];
		for(z=1;z<=a[y][0];z++)
		{
			xx=a[y][z];
			if((viz[xx]==0) && (d[xx]>c[y][z]))
			{
				d[xx]=c[y][z];
				pred[xx]=y;
			}
		}
	}
	printf("%d\n%d\n",costuri,n-1);
	for(int i=1;i<n;i++)
		printf("%d %d\n",s[i],t[i]);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	//afisareproba();
	prim(1);
	return 0;
}