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

const int N = 200001;
const int M = 400001;

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;
}

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

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



void citire()
{
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= m; ++i)
		scanf("%d%d%d",&muchie[i].a,&muchie[i].b,&muchie[i].cost);
}

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; ++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()
{
	printf("%d\n",cost_total);
	printf("%d\n",n_muchie_select);
	for (int i = 1; i <= n_muchie_select; ++i)
		printf("%d %d\n",muchie_select[i].a,muchie_select[i].b);
}

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