#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define MAX_N 400000
using namespace std;
int a[MAX_N],x[MAX_N],y[MAX_N],c[MAX_N],i,n,m,s,d[MAX_N];
vector <int> v;
int grupeaza(int i)
{
	if (a[i]==i) return i;
	a[i]=grupeaza(d[i]);
	return a[i];
}
void collide(int i,int j)
{
	a[grupeaza(i)]=grupeaza(j); 
}
bool cmp(int x,int y)
{
	return(c[x]<c[y]);	
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d %d %d\n",&x[i],&y[i],&c[i]);
		d[i]=i;
	}

	for(i=1;i<=n;i++) a[i]=i;
	for(i=1;i<=n;i++) a[i]=i;
	sort(d+1,d+m+1,cmp);
	for(int i = 1;i <= m;i++)
	{
		if (grupeaza(x[d[i]])!=grupeaza(y[d[i]])){
			s+=c[d[i]];
			collide(x[d[i]],y[d[i]]);
			v.pb(d[i]);
		}
	}
	printf("%d\n",s);
	printf("%d\n",n-1);
	for(i=0;i<n-1;i++)
		printf("%d %d\n",x[v[i]],y[v[i]]);
	return 0;
}