#include<stdio.h>

#include<algorithm>

#include<vector>

#define pb push_back



using namespace std;



const int maxn = 400100;



int GR[maxn],X[maxn],Y[maxn],C[maxn];

int N,M,ANS,IND[maxn];

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",&N,&M);

	for(int i = 1;i <= M;++i)

	{

		scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);

		IND[i] = i;

	}



	for(int i = 1;i <= N; ++i) GR[i] = i;

	for(int i = 1;i <= N; ++i) GR[i] = i;

	sort(IND + 1,IND + M + 1,cmpf);

	for(int 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.pb(IND[i]);

		}

	}

	printf("%d\n",ANS);

	printf("%d\n",N - 1);

	for(int i = 0;i < N - 1; ++i)

		printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);

	return 0;

}