#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
const int maxn=400100;
long grup[maxn],x[maxn],y[maxn],c[maxn],i,n,m,s,d[maxn];
vector <int> v;
inline int grupeaza(int i)
{
	if (grup[i]==i) return i;
	grup[i]=grupeaza(grup[i]);
	return grup[i];
}
inline void uneste(int i,int j)
{
	grup[grupeaza(i)] = grupeaza(j); 
}
bool cmp(int i,int j)
{
	return(c[i]<c[j]);	
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d\n",&x[i],&y[i],&c[i]);
		d[i]=i;
	}
	for(i=1;i<=n;i++) grup[i]=i;
	for(i=1;i<=n;i++) grup[i]=i;
	sort(d+1,d+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		if (grupeaza(x[d[i]])!=grupeaza(x[d[i]]))
		{
			s+=c[d[i]];
			uneste(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;
}