#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 400006
int GR[NMAX],x[NMAX],y[NMAX],cost[NMAX];
int n,m,sum, ord[NMAX];
vector<int> SOL;

int grup(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grup(GR[i]);
	return GR[i];
}

void reuneste(int i,int j)
{
	GR[grup(i)] = grup(j); 
}

bool cond(int a,int b)
{
	return(cost[a] < cost[b]);	
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(int i = 1;i <= m;++i)
	{
		scanf("%d %d %d\n",&x[i],&y[i],&cost[i]);
		ord[i] = i;
	}

	for(int i=1;i<=n; ++i) GR[i] = i;	
	sort(ord+1,ord+m+1, cond);
	
	sum=0;
	for(int i=1;i<=m; ++i)
	{
		if (grup(x[ord[i]]) != grup(y[ord[i]]))
		 {
			sum+= cost[ord[i]];
			reuneste(x[ord[i]],y[ord[i]]);
			SOL.push_back(ord[i]);
	 	 } 
	}
	
	printf("%d\n",sum);
	printf("%d\n",n - 1);
	for(int i = 0;i<n-1; ++i)
		printf("%d %d\n",x[SOL[i]],y[SOL[i]]);
	
	return 0;
}