#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 400100
using namespace std;
int grup[maxn],x[maxn],y[maxn],c[maxn],i;
int n,m,s,d[maxn];
vector <int> v;
int grupeaza(int i)
{
	if (grup[i] == i) return i;
	grup[i] = grupeaza(grup[i]);
	return grup[i];
}
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;
	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;
}