#include<stdio.h>
#include<algorithm>
#define Nmax 200010
#define Mmax 400010
using namespace std;
int n,m,viz[Nmax],costtot,nr,nrm,sol[Mmax];
struct heap
{
	int c,x,y;
}h[Mmax];
struct nod
{
	int inf;
	nod *urm;
}*lis[Nmax];

int compar(heap a,heap b)
{
	return (a.c<b.c);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	int i,j;
	nod *p;
	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=0;i<m;i++)
	{
		if(viz[h[i].x]==0 && viz[h[i].y]!=0)
		{
			viz[h[i].x]=viz[h[i].y];
			p=new nod;
			p->inf=h[i].x;
			p->urm=lis[viz[h[i].y]];
			lis[viz[h[i].y]]=p;
			costtot+=h[i].c;
			sol[++nrm]=i;
		}
		else
			if(viz[h[i].y]==0 && viz[h[i].x]!=0)
			{
				viz[h[i].y]=viz[h[i].x];
				costtot+=h[i].c;
				p=new nod;
				p->inf=h[i].y;
				p->urm=lis[viz[h[i].x]];
				lis[viz[h[i].x]]=p;
				sol[++nrm]=i;
			}
			else
				if(viz[h[i].x]==0 && viz[h[i].y]==0)
				{
					nr++;
					viz[h[i].x]=nr;
					viz[h[i].y]=nr;
					costtot+=h[i].c;
					p=new nod;
					p->inf=h[i].x;
					p->urm=lis[nr];
					lis[nr]=p;
					p=new nod;
					p->inf=h[i].y;
					p->urm=lis[nr];
					lis[nr]=p;
					sol[++nrm]=i;
				}
				else
					if(viz[h[i].x]!=0 && viz[h[i].y]!=0 && viz[h[i].x]!=viz[h[i].y])
					{
						int aj;
						nod *q;
						aj=viz[h[i].x];
						for(p=lis[aj];p!=NULL;p=p->urm)
						{
							viz[p->inf]=viz[h[i].y];
							q=p;
						}
						q->urm=lis[viz[h[i].y]];
						lis[viz[h[i].y]]=q;
						costtot+=h[i].c;
						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;
}