using namespace std;
#include<cstdio>
#define nmax 400010
struct muchie { int x,y,c;};
muchie m[nmax];
int n,mu,t[nmax],h[nmax],nr[nmax];

int arb(int i)
{
	while(t[i]) i=t[i];
	return i;
}

int poz (int i,int j)
{
	int i1=0,j1=-1,aux;
	muchie aux2;
	while(i<j)
	{
		if(m[i].c>m[j].c)
		{
			aux2=m[i]; m[i]=m[j]; m[j]=aux2;
			aux=i1; i1=-j1; i1=-aux;
		}
		i=i+i1;
		j=j+j1;
	}
	return i;
}
			

void sort(int x, int y)
{
	if(x<y)
	{
	int k=poz(x,y);
	sort(x,k-1);
	sort(k+1,y);
	}
}

int main()
{
	int cost=0,i;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&mu);
	for(i=0;i<mu;i++)
		scanf("%d%d%d",&m[i].x,&m[i].y,&m[i].c);
	sort(0,mu-1);	
	int k=0;
	for(i=1;i<n;i++)
	{
		while(arb(m[k].x)==arb(m[k].y)) k++;
		cost=cost+m[k].c;
		nr[i]=k;
		if(h[m[k].x]==h[m[k].y])
		{
			t[m[k].x]=m[k].y;
			h[m[k].y]++;
		}
		else if(h[m[k].x]>h[m[k].y]) t[m[k].y]=m[k].x;
			 else t[m[k].x]=m[k].y;
		k++;
	}
	printf("%d\n%d\n",cost,n-1);
	for(i=1;i<n;i++)
		printf("%d %d\n",m[nr[i]].x,m[nr[i]].y);
	return 0;
}