#include<stdio.h>
#include<algorithm>
#define Nmax 200010
#define Mmax 400010
using namespace std;

int T[Nmax],H[Nmax],n,m,i,Apm[Nmax],Cost,Tx,Ty,N;
struct muchie {int x,y,cost;} v[Nmax],Arb[Nmax];

int cmp(muchie a, muchie b)
{
	return a.cost < b.cost;
}

int find (int x)
{
	int R=x,y;
	
	for(; R!=T[R]; R=T[R]);

	// compresia drumurilor
	for(; x!=T[x]; )
	{
		y=T[x];
		T[x]=R;
		x=y;
	}
	return R;
}

void uneste (int x, int y)
{
	if(H[x]>=H[y]) T[y]=x;
		else       T[x]=y; 
 
		if(H[x]==H[y]) H[x]++;
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
		scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
	
	sort(v+1,v+m+1,cmp);
	
	for(i=1;i<=n;i++)
	{
		T[i]=i;
		H[i]=1;
	}
	
	for(i=1;i<=m;i++)
	{
		Tx=find(v[i].x);
		Ty=find(v[i].y);
		if(Tx!=Ty) { Cost+=v[i].cost; uneste(Tx,Ty); Arb[++N]=v[i];}
	}
	printf("%d\n%d\n",Cost,n-1);
	for(i=1;i<=N;i++)
		printf("%d %d\n",Arb[i].x,Arb[i].y);
	return 0;
}