#include<stdio.h>
#include<algorithm>
#include<vector>


using namespace std;

const int maxn = 400100;//sau #define int maxn=400100

int GR[maxn],X[maxn],Y[maxn],COST[maxn];
int N,M,REZ,INDICE[maxn];
vector<int> APM;

int Padure(int i)
{
	if (GR[i] == i) return i;
	GR[i] = Padure(GR[i]);

	return GR[i];
}

void reuniune(int i,int j)
{
	GR[Padure(i)] = Padure(j); //reunim padurea i cu padurea j
}

bool cmp(int i,int j)
{
	return(COST[i] < COST[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],&COST[i]);
		INDICE[i] = i;
	}

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


	sort(INDICE + 1,INDICE + M + 1,cmp);//sortam vectorul indice dupa vectorul cost


	for(int i = 1;i <= M; ++i)
	{
		if (Padure(X[INDICE[i]]) != Padure(Y[INDICE[i]]))
		    {
		        	REZ += COST[INDICE[i]];//daca nodurile - x[indice[i]] si y[indice[j]] fac parte din paduri distincte
					                       //adaugam costul muchiei la rezultat (REZ)
			        reuniune(X[INDICE[i]],Y[INDICE[i]]); //reunim padurile
			        APM.push_back(INDICE[i]);            //adaugam la solutie muchia
		}
	}
	printf("%d\n",REZ);
	printf("%d\n",N - 1);
	for(int i = 0;i < N - 1; ++i)
		printf("%d %d\n",X[APM[i]],Y[APM[i]]);
	return 0;
}