#include <iostream>
#include <fstream>
#include <stdlib.h>
//#pragma warning(disable: 0167)

using namespace std;

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

struct muc
{
	int x, y, c;
};

int n, m;
muc muchii[100001];

void ctr()
{
	fin >> n >> m;

	int x, y, c;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		muchii[i].x = x;
		muchii[i].y = y;
		muchii[i].c = c;
	}
}

void ord()
{
	muc aux;
	int ok = 1;
	while (ok == 1)
	{
		ok = 0;
		for (int i = 1; i < m; ++i)
		{
			if (muchii[i].c > muchii[i + 1].c)
			{
				aux = muchii[i];
				muchii[i] = muchii[i + 1];
				muchii[i + 1] = aux;
				ok = 1;
			}
		}
	}
}



int comp[10001], nr_sol, sum_sol;
muc sol[100001];

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

int cmp(const void *p, const void *q)
{
	int c1, c2;

	c1 = ((struct muc *)p)->c;
	c2 = ((struct muc *)q)->c;

	return c1 - c2;
}

void KRUSK()
{
	ord();
	init();

	qsort(muchii, m, sizeof(muc), cmp);

	int nr_folos = 0;
	int i = 1;
	while (nr_folos < n - 1)
	{
		int x, y;
		int a;

		x = muchii[i].x;
		y = muchii[i].y;
		a = comp[y];

		if (comp[x] != comp[y])
		{
			for (int j = 1; j <= n; ++j)
			{
				if (comp[j] == a)comp[j] = comp[x];
			}
			nr_folos++;
			nr_sol++;
			sol[nr_sol] = muchii[i];
			sum_sol += muchii[i].c;
		}
		i++;
	}
}

void afis()
{
	fout << sum_sol << '\n';
	fout << nr_sol << '\n';
	for (int i = 1; i <= nr_sol; ++i)
	{
		fout << sol[i].x << " " << sol[i].y << '\n';
	}
}


int main()
{
	ctr();

	KRUSK();

	afis();

	return 0;
}