#include<stdio.h>
#include<algorithm>
#define NMAX 200005
using namespace std;
int n,m,x[NMAX],y[NMAX],c[NMAX],d[NMAX],tata[NMAX],ordin[NMAX],v[NMAX];
int cmp(int a, int b)
{
	if(c[a] < c[b]) return 1;
	return 0;
}
void grupeaza(int x)
{
	tata[x] = x;
	ordin[x] = x;
}

int go(int x)
{
	if(tata[x] == x) 
		return tata[x];
	else
	{
		tata[x]=go(tata[x]);
		return tata[x];
	}
}
void reuniune(int x1,int y1)
{
	if(ordin[x1]>ordin[y1])
		{
			tata[y1]=x1;
			ordin[x1]+=ordin[y1];
		}
	  else if(ordin[x1]<=ordin[y1])
		  {
			  tata[x1]=y1;
			  ordin[y1]+=ordin[x1];
		  }
}
int main()
{ 
  	int i,rez1=0,rez2=0,x1,y1;
	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",&x[i],&y[i],&c[i]);
		d[i]=i;
	}
	for(i=1;i<=n;i++)
		grupeaza(i);
	sort(d+1,d+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		x1=go(x[d[i]]);
		y1=go(y[d[i]]);
		if(x1!=y1)
		{
			reuniune(x1,y1);
			rez2++;
			v[rez2]=d[i];
			rez1+=c[d[i]];
		}
	}
	printf("%d\n%d\n",rez1,rez2);
	for(i=1;i<=rez2;i++)
		printf("%d %d\n",y[v[i]],x[v[i]]);
	return 0;
}