#include<cstdio>
#include<algorithm>
using namespace std;

struct edge
{
	int x,y,c;
	edge()
		{
			x=y=c=0;
		}
	edge (int xx,int yy,int cc)
		{
			x=xx;
			y=yy;
			c=cc;
		}
	bool operator<(const edge e)const
		{
			return c<e.c;
		}
}     v[400005];
int  uf[400005];
int rmx[400005];
int rmy[400005];
int   r[400005];
int ans;

int find (int x)
{
	if(uf[x]==x)
		return x;
	uf[x]=find (uf[x]);
	return uf[x];
}

void join (int x,int y,int c)
{
	int rx=find (x);
	int ry=find (y);
	if(rx==ry)
		return;
	if(r[rx]<r[ry])
		uf[rx]=ry;
	else if(r[rx]>r[ry])
		uf[ry]=rx;
	else{
		uf[ry]=rx;
		r[rx]++;
	}
	ans+=c;
}

int main()
{
	freopen ("apm.in","r",stdin);
	freopen ("apm.out","w",stdout);
	int n,m;
	scanf ("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int x,y,c;
		scanf ("%d%d%d",&x,&y,&c);
		v[i]=edge (x,y,c);
	}
	sort (v,v+m);
	for(int i=1;i<=n;i++)
		uf[i]=i;
	int left=n-1;
	int i=0;
	for(;left&&i<m;i++)
		if(find (v[i].x)!=find (v[i].y)){
			join (v[i].x,v[i].y,v[i].c);
			left--;
			rmx[left]=v[i].x;
			rmy[left]=v[i].y;
		}
	printf ("%d\n%d\n",ans,n-1);
	for(int i=0;i<n-1;i++)
		printf ("%d %d\n",rmx[i],rmy[i]);
	return 0;
}