#include <fstream>
#include <vector>

#include <algorithm>

#define MAX_N 200005

using namespace std;

struct Muchie
{
	int nod1;
	int nod2;
	int cost;
	bool d;
};

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

int n, m;
vector<Muchie> muchii;
int conexe[MAX_N] = { 0 };

int costMinim = 0;
int nMuchii = 0;

void Kruskal()
{
	int muchie = 0;
	int k = 0;

	int minM;
	int maxM;

	for (int i = 1; i <= n; i++)
	{
		conexe[i] = i;
	}
	
	while (muchie < n - 1)
	{
		if (conexe[muchii[k].nod1] != conexe[muchii[k].nod2])
		{
			muchii[k].d = true;

			costMinim += muchii[k].cost;

			minM = min(conexe[muchii[k].nod1], conexe[muchii[k].nod2]);
			maxM = max(conexe[muchii[k].nod1], conexe[muchii[k].nod2]);

			for (int i = 1; i <= n; i++)
			{
				if (conexe[i] == maxM)
				{
					conexe[i] = minM;
				}
			}

			muchie++;
		}

		k++;
	}

	nMuchii = muchie;
}

int main(void)
{
	fin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		Muchie muc = Muchie();
		
		fin >> muc.nod1 >> muc.nod2 >> muc.cost;
		muc.d = false;

		muchii.push_back(muc);
	}

	sort(muchii.begin(), muchii.end(), [](Muchie m1, Muchie m2) 
	{
		return m1.cost < m2.cost;
	});

	Kruskal();

	fout << costMinim << endl << nMuchii << endl;

	for (int i = 0; i < m; i++)
	{
		if (muchii[i].d)
		{
			fout << muchii[i].nod1 << " " << muchii[i].nod2 << endl;
		}
	}

	fin.close();
	fout.close();

	return 0;
}