#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];

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;
	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];
			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;
				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;
					sol[++nrm]=i;
				}
				else
					if(viz[h[i].x]!=0 && viz[h[i].y]!=0 && viz[h[i].x]!=viz[h[i].y])
					{
						for(j=1;j<=n;j++)
							if(viz[j]==viz[h[i].x])
								viz[j]=viz[h[i].y];
						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;
}