#include<stdio.h>
#include<algorithm>
#include<vector>
#define nmax 400010
using namespace std;
int n,m,a,pos[nmax],g[nmax],x[nmax],y[nmax],z[nmax];
vector<int>v;
int gr(int);
void reun(int,int);
int cmpf(int,int);
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x[i],&y[i],&z[i]);
		pos[i]=i;
	}
	for(i=1;i<=n;i++)g[i]=i;
	sort(pos+1,pos+m+1,cmpf);
	for(i=1;i<=m;i++)
	{
		if(gr(x[pos[i]])!=gr(y[pos[i]]))
		{
			a=a+z[pos[i]];
			reun(x[pos[i]],y[pos[i]]);
			v.push_back(pos[i]);
		}
	}
	printf("%d\n",a);
	printf("%d\n",n-1);
	for(i=0;i<n-1;i++)
		printf("%d %d\n",y[v[i]],x[v[i]]);
	return 0;
}
int gr(int i)
{
	if(g[i]==i)
		return i;
	g[i]=gr(g[i]);
	return g[i];
}
void reun(int i,int j)
{
	g[gr(i)]=gr(j);
}
int cmpf(int i,int j)
{
	return(z[i]<z[j]);
}