#include<stdio.h>
#include<algorithm>
#define Nmax 200100
#define Mmax 400100
using namespace std;
int n,m,viz[Nmax],costtot,nr,nrm,sol[Mmax],t[Nmax];
struct heap
{
	int c,x,y;
}h[Mmax];

int compar(heap a,heap b)
{
	return (a.c<b.c);
}
int radacina(int x)
{
	if(x!=t[x])
	{	
		t[x]= radacina(t[x]);
		return t[x];
	}
	else
		return x;
	
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	int i,nca,ncb;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++)
		scanf("%d %d %d",&h[i].x,&h[i].y,&h[i].c);
	sort(h,h+m,compar);
	for(i=1;i<=n;i++)
			t[i]=i;
	for(i=0;i<m;i++)
	{
		nca=radacina(h[i].x);
		ncb=radacina(h[i].y);
		if(nca!=ncb)
		{
			costtot+=h[i].c;
			t[ncb]=t[h[i].x];
			sol[++nrm]=i;
		}
	}
	printf("%d\n%d\n",costtot,nrm);
	for(i=1;i<=nrm;i++)
		printf("%d %d\n",h[sol[i]].x,h[sol[i]].y);
	return 0;
}