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

ifstream in("apm.in");
ofstream out("apm.out");

const int N = 200006;
const int M = 400006;

struct mchie
{
	int a,b,cost;
};

int n;
int tata[N]; //int nr_rad; //nr_rad ar fi putut fi folosit pt verificarea conexitatii
mchie muchie[M]; int m;
int ind_muchie[M];
mchie muchie_select[M]; int n_muchie_select;
int cost_total = 0;

int radacina(int x)
{
	if(tata[x] == 0)
		return x;
	return tata[x] = radacina(tata[x]);
}

inline bool e_in_aceeasi_multime(int x, int y)
{
	return radacina(x) == radacina(y);
}

inline void reuniune(int x, int y)
{
	tata[radacina(x)] = radacina(y);
}

void citire()
{
	in>>n>>m;
	for (int i = 1; i <= m; ++i)
		in>>muchie[i].a>>muchie[i].b>>muchie[i].cost;
}

void initializare_sortare()
{
	for (int i = 1; i <= m; ++i)
		ind_muchie[i] = i;
}

inline bool muchii_crescatoare(int ind1, int ind2)
{
	return muchie[ind1].cost <= muchie[ind2].cost;
}


void apm()
{
	initializare_sortare();
	sort(ind_muchie+1,ind_muchie+m+1, muchii_crescatoare);
	for (int i = 1; i <= m && n_muchie_select <= n-1; ++i)
		if (!e_in_aceeasi_multime(muchie[ ind_muchie[i] ].a,muchie[ ind_muchie[i] ].b))
		{
			reuniune(muchie[ ind_muchie[i] ].a,muchie[ ind_muchie[i] ].b);
			muchie_select[++n_muchie_select] = muchie[ ind_muchie[i] ];
			cost_total += muchie[ ind_muchie[i] ].cost;
		}
}

void scriere()
{
	out<<cost_total<<"\n";
	out<<n_muchie_select<<"\n";
	for (int i = 1; i <= n_muchie_select; ++i)
		out<<muchie_select[i].a<<" "<<muchie_select[i].b<<"\n";
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	apm();
	scriere();
	return 0;
}