#include<stdio.h>
#include<vector>
#include<algorithm>
#define NMAX 400002
#define MMAX 200002
using namespace std;
int M1[MMAX],M2[MMAX],M3[MMAX],I[MMAX];
int R[NMAX];
vector < int > SOL;
//cool stuff
int find(int a)
{
	if( R[a]==a ) return a;
	R[a]=find(R[a]);
	return R[a];
}

void unite(int a,int b)
{
	R[find(a)]=find(b);
	find(a);
}

inline bool cmp(const int i,const int j)
{
	return M3[i]<M3[j];
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	int N,M,ANS=0;
	scanf("%d%d",&N,&M);
	
	int i,a1,a2,a3;
	for(i=1; i<=M; ++i){
		scanf("%d%d%d\n",&a1,&a2,&a3);
		M1[i]=a1;M2[i]=a2;M3[i]=a3;I[i]=i;
	}
	for(i=1; i<=N; ++i)R[i]=i;
	sort(I+1,I+M+1,cmp);
	for(i=1; i<=M; ++i)
	{
		if( find( M1[I[i]] ) != find( M2[I[i]] ) )
		{
			unite(M1[I[i]],M2[I[i]]);
			ANS+=M3[I[i]];SOL.push_back(I[i]);
		}
	}
	printf("%d\n%d\n",ANS,N-1);
	vector< int >::iterator it;
	for(it=SOL.begin(); it!=SOL.end(); ++it)
		printf("%d %d\n",M1[*it],M2[*it]);
	return 0;
}