#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie
{
	int nod1, nod2, cost;
}G[200005];

pair <int, int> sol[200005];
int n, m, sum, tata[200005], Rang[200005], nr;

bool cmp(muchie x, muchie y)
{
	return x.cost < y.cost;
}

void Unite(int x, int y)
{
	if (Rang[x] == Rang[y])
	{
		tata[y] = x;
		Rang[x]++;
	}
	else
		if (Rang[x] > Rang[y])
		tata[y] = x;
	else
		tata[x] = y;
}

int Tata(int nod)
{
	while (nod != tata[nod]) 
		nod = tata[nod];
	return nod;
}

int main()
{
	f >> n >> m;
	int i;
	for (i = 1; i <= m; i++)
		f >> G[i].nod1 >> G[i].nod2 >> G[i].cost;
	for (i = 1; i <= n; i++) 
		tata[i] = i;
	sort(G + 1, G + 1 + m, cmp);
	for (i = 1; i <= m; i++)
		if (Tata(G[i].nod1) != Tata(G[i].nod2))
		{
			Unite(Tata(G[i].nod1), Tata(G[i].nod2));
			sol[++nr] = make_pair(G[i].nod1, G[i].nod2);
			sum += G[i].cost;
		}
	g << sum <<endl << nr <<endl;
	for (i = 1; i <= nr; i++)
		g << sol[i].first << " " << sol[i].second << endl;
	return 0;
}