#include <cstdio>
#include <algorithm>
#include <vector>
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200100
#define MMAX 400100
using namespace std;
int N, M;
int X[MMAX], Y[MMAX], C[MMAX];
int Ord[MMAX];
int GR[NMAX];
int val = 0;
vector<int> Mu;

void citire()
{
	scanf("%d%d",&N, &M);
	for(int i = 1 ; i <= M ;i++)
	{
		scanf("%d %d %d",&X[i], &Y[i] ,&C[i]);
		Ord[i] = i;
	}
}

bool cmp(int a,int b)
{
	return C[a] < C[b];
}

void init()
{
	for(int i = 1 ; i <= N ; i++)
		GR[i] = i;
}

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)] = GR[grupa(j)];
}

void scrie()
{
	printf("%d\n",val);
	printf("%d\n",N - 1);
	for(int i = 0 ; i < N - 1 ; i++)
		printf("%d %d\n",X[Mu[i]],Y[Mu[i]]);
}

int main()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	citire();
	sort(Ord + 1,Ord + M + 1,cmp);
	init();
	for(int i = 1 ; i <= M ;i++)
		if(grupa(X[Ord[i]]) != grupa(Y[Ord[i]]))
		{
			reuniune(X[Ord[i]], Y[Ord[i]]);
			val += C[Ord[i]];
			Mu.push_back(Ord[i]);
		}
	/*for(int i = 0 ; i != Mu.size() ; i++)
		printf("%d ",Mu[i]);*/
	scrie();
	
	return 0;
}