#include <algorithm>
#include <stdio.h>
#include <vector>

#define pb push_back
#define f first
#define s second

using namespace std;

int nrNod, nrVert;
vector <int> tata;
vector <pair <int, int> > vctSol;
vector <pair <int, pair <int, int> > > vctVert;

int radArb(int nod)
{
	if (tata[nod] == nod)
		return nod;

	tata[nod] = radArb(tata[nod]);

	return tata[nod];
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d", &nrNod, &nrVert);

	for (int i = 0; i < nrVert; i++)
	{
		int node1, node2, costDrum;
		scanf("%d %d %d", &node1, &node2, &costDrum);

		vctVert.pb(make_pair(costDrum, make_pair(node1, node2)));
	}

	sort(vctVert.begin(), vctVert.end());

	for (int i = 0; i <= nrNod; i++)
		tata.pb(i);

	int sumaLung = 0;

	for (int i = 0; i < nrVert; i++)
	{
		if (radArb(vctVert[i].s.f) != radArb(vctVert[i].s.s))
		{
			sumaLung += vctVert[i].f;
			vctSol.pb(make_pair(vctVert[i].s.f, vctVert[i].s.s));
			tata[tata[vctVert[i].s.s]] = tata[vctVert[i].s.f];
		}
	}

	printf("%d\n", sumaLung);
	printf("%d\n", vctSol.size());
	for (int i = 0; i < vctSol.size(); i++)
		printf("%d %d\n", vctSol[i].f, vctSol[i].s);

	fclose(stdin);
	fclose(stdout);
	return 0;
}