#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;
mchie muchie_select[M]; int n_muchie_select;
int cost_total = 0;

/*
int radacina(int x)
{
	int nod = x,rad,aux;
	while (tata[nod] != 0)
		nod = tata[nod];
	rad = nod;
	nod = x;
	while (tata[nod] != 0)
	{
		aux = tata[nod];
		tata[nod] = rad;
		nod = aux;
	}
	return rad;
}
*/
int radacina(int x)
{
	if(tata[x] == 0)
		return x;
	tata[x] = radacina(tata[x]);
	return 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[(tata[x] == 0 ? x : tata[x])] = (tata[y] == 0 ? y : tata[y]);
}

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

inline bool muchii_crescatoare(mchie m1, mchie m2)
{
	return m1.cost <= m2.cost;
}

void apm()
{
	sort(muchie+1,muchie+m+1, muchii_crescatoare);
	for (int i = 1; i <= m && n_muchie_select <= n-1; ++i)
		if (!e_in_aceeasi_multime(muchie[i].a,muchie[i].b))
		{
			reuniune(muchie[i].a,muchie[i].b);
			muchie_select[++n_muchie_select] = muchie[i];
			cost_total += 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;
}