#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

const char infile[]="apm.in";
const char outfile[]="apm.out";

#define NMAX 200010
#define MMAX 400010

struct Nod
{
	Nod* tata;
	int indice;
	int rang;
};

Nod A[NMAX];

struct muchie
{
	int cost;
	int x;
	int y;
};

bool f(muchie A,muchie B)
{
	if (A.cost<B.cost)
		return 1;
	else return 0;
}

muchie B[MMAX];

int C;
int N;
int M;

vector<pair<int,int> > V;


int parinte(int x)
{
	int a=x;
	while(A[x].tata!=NULL)
	{
		x=A[x].tata->indice;
	}
	int b;
	while(A[a].tata!=NULL)
	{
		b=a;
		a=A[a].tata->indice;
		A[b].tata=&A[x];
	}
	return x;
}

void uneste(int x,int y)
{
	int a=parinte(x);
	int b=parinte(y);
	if(A[a].rang>A[b].rang)
	{
		A[b].tata=&A[a];
		A[a].rang+=A[b].rang;
	}
	else
	{
		A[a].tata=&A[b];
		A[b].rang+=A[a].rang;
	}
}

void init()
{
	for(int i=1;i<=N;i++)
	{
		A[i].indice=i;
		A[i].rang=1;
		A[i].tata=NULL;
	}
}

void citire()
{
	fstream fin(infile,ios::in);
	fin>>N;
	fin>>M;
	int x,y,c;
	for(int i=1;i<=M;i++)
	{
		fin>>x>>y>>c;
		B[i].x=x;
		B[i].y=y;
		B[i].cost=c;
	}
	fin.close();
	init();
}

void proc()
{
	int k=1;
	int a,b;
	for(int i=1;i<=M;i++)
	{
		a=parinte(B[i].x);
		b=parinte(B[i].y);
		if(a!=b)
		{
			uneste(a,b);
			C+=B[i].cost;
			V.push_back(make_pair(B[i].x,B[i].y));
			k++;
			if (k==N) break;
		}

	}
}

void afisare()
{
	fstream fout(outfile,ios::out);
	fout<<C<<"\n";
	fout<<N-1<<"\n";
	for(vector<pair<int,int> >::iterator itr=V.begin();itr!=V.end();itr++)
		fout<<itr->second<<" "<<itr->first<<"\n";

	fout.close();
}

int main()
{
	citire();
	sort(B+1,B+M+1,f);
	proc();
	afisare();
}