#include<cstdio>
#include<vector>
#include<algorithm>
#define NMAX 400100
using namespace std;
int GR[NMAX],X[NMAX],Y[NMAX],C[NMAX];
int i,N,M,ANS=0,IND[NMAX];
vector<int> VANS;
int grupa(int i)
{
	if(GR[i]==i) return i;
	GR[i]=grupa(GR[i]);
	return GR[i];
}
void reuniune(int i,int j)
{
	GR[grupa(i)]=grupa(j);
}
bool cmpf(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,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d %d",&X[i],&Y[i],&C[i]);
		IND[i]=i;
	}
	for(i=1;i<=N;++i) GR[i]=i;
	sort(IND+1,IND+M+1,cmpf);
	for(i=1;i<=M;++i)
	{
		if(grupa(X[IND[i]])!=grupa(Y[IND[i]]))
		{
			ANS+=C[IND[i]];
			reuniune(X[IND[i]],Y[IND[i]]);
			VANS.push_back(IND[i]);
		}
	}
	printf("%d\n",ANS);
	printf("%d\n",N-1);
	for(i=0;i<N-1;++i)
		printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);
	return 0;
}