#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define max 400100

int gr[max],x[max],y[max],c[max],ind[max],n,m,ans;
vector<int> val;

int grupa ( int i )
{
	if ( gr[i]==i) return i;
	gr[i]=grupa(gr[i]);
	return gr[i];
}

void reun(int a,int b)
{
	gr[grupa(a)]=grupa(b);
}
bool comp(int a,int b)
{
	return c[a]<c[b];
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d ",&x[i],&y[i],&c[i]);
		ind[i]=i;
	}
	for(int i=1;i<=n;i++) gr[i]=i;
	sort(ind+1,ind+m+1,comp);
	for(int i=1;i<=m;i++)
	{
		if( grupa(x[ind[i]]) != grupa(y[ind[i]]) )
		{
			ans+=c[ind[i]]; 
			reun(x[ind[i]],y[ind[i]]);
			val.push_back(ind[i]);
		}
	}
	printf("%d\n%d\n",ans,n-1);
	for(int i=0;i<n-1;i++)
		printf("%d %d\n",x[val[i]],y[val[i]]);
}