#include <iostream>
#include <fstream>
#include <unordered_map>
#include <list>
#include <queue>
#include <stack>

using namespace std;

ifstream f("apm.in");
ofstream o("apm.out");

class Graf {
	int noduri, muchii;
	unordered_map<int, list<int>>vecini;
	unordered_map<int, bool> vizitat;
	stack<int>stiva_sortare_topologica;
	unordered_map<int, list<int>>vecini_transp;
	unordered_map<int, int>vizitat_transp;
	stack<int>timp_vizitare;
	unordered_map<int, list<int>>componente_tare_conexe;

public:
	Graf(int n, int m);
	int get_noduri();
	int get_muchii();
	int get_vizitat(int nod);
	void adauga_muchie_neorientat(int nod1, int nod2);
	void adauga_muchie_orientat(int nod1, int nod2);
	void sorteaza();
	void dfs(int nod);
	void componente_conexe();
	void bfs(int nod);
	void sortare_topologica();
	void tool_sortare_topologica(int nod);
	void dfs_graf_transpus(int nod, int rezultat);
	void tare_conexitate();
	void apm();
};

Graf::Graf(int n, int m)
{
	this->noduri = n;
	this->muchii = m;
	for (int i = 1; i <= n; i++)
		vizitat[i] = vizitat_transp[i] = 0;
}

int Graf::get_noduri()
{
	return this->noduri;
}

int Graf::get_muchii()
{
	return this->muchii;
}

int Graf::get_vizitat(int nod)
{
	return vizitat[nod];
}

void Graf::adauga_muchie_neorientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini[nod2].push_back(nod1);
}

void Graf::adauga_muchie_orientat(int nod1, int nod2)
{
	vecini[nod1].push_back(nod2);
	vecini_transp[nod2].push_back(nod1);
}

void Graf::sorteaza()
{
	for (int i = 1; i <= noduri; i++)
		vecini[i].sort();
}

void Graf::dfs(int nod)
{
	//cout << nod << " ";
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			dfs(*i);

	timp_vizitare.push(nod);
}

void Graf::dfs_graf_transpus(int nod, int rezultat)
{
	componente_tare_conexe[rezultat].push_back(nod);

	vizitat_transp[nod] = 1;

	for (auto i = vecini_transp[nod].begin(); i != vecini_transp[nod].end(); i++)
		if (vizitat_transp[*i] != 1)
			dfs_graf_transpus(*i, rezultat);
}

void Graf::componente_conexe()
{
	int sol = 0;
	sorteaza();

	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
		{
			sol += 1;
			dfs(i);
		}

	o << sol;
}

void Graf::tare_conexitate()
{
	int rezultat = 0;

	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
			dfs(i);

	while (timp_vizitare.size())
	{
		if (vizitat_transp[timp_vizitare.top()] != 1)
		{
			rezultat++;
			dfs_graf_transpus(timp_vizitare.top(), rezultat);
		}
		timp_vizitare.pop();
	}
	o << rezultat;

	for (int i = 1; i <= rezultat; i++)
	{
		o << "\n";
		//componente_tare_conexe[i].sort();
		for (auto j = componente_tare_conexe[i].begin(); j != componente_tare_conexe[i].end(); j++)
			o << *j << " ";
	}
}

void Graf::bfs(int nod)
{
	int start = nod;
	queue<int>coada;
	vizitat[nod] = 1;
	coada.push(nod);
	unordered_map<int, int>distanta;

	for (int i = 1; i <= noduri; i++)
		distanta[i] = 0;

	while (coada.size())
	{
		nod = coada.front();
		//cout << nod << " ";
		coada.pop();
		for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
			if (!vizitat[*i])
			{
				vizitat[*i] = 1;
				coada.push(*i);
				distanta[*i] = distanta[nod] + 1;
			}
	}
	for (int i = 1; i <= noduri; i++)
		if (i != start && distanta[i] == 0)
			o << "-1" << " ";
		else
			o << distanta[i] << " ";
}

void Graf::tool_sortare_topologica(int nod)
{
	vizitat[nod] = 1;

	for (auto i = vecini[nod].begin(); i != vecini[nod].end(); i++)
		if (vizitat[*i] != 1)
			tool_sortare_topologica(*i);

	stiva_sortare_topologica.push(nod);
}

void Graf::sortare_topologica()
{
	for (int i = 1; i <= noduri; i++)
		if (vizitat[i] != 1)
			tool_sortare_topologica(i);

	while (stiva_sortare_topologica.size())
	{
		o << stiva_sortare_topologica.top() << " ";
		stiva_sortare_topologica.pop();
	}
}

void Graf::apm()
{
	struct muchie
	{
		int st, dr, cost;
	};

	unordered_map <int, muchie> v;

	for (int i = 1; i <= muchii; i++)
	{
		f >> v[i].st >> v[i].dr >> v[i].cost;
	}

	for(int i = 1; i < muchii; i++)
		for(int j = i + 1; j <= muchii; j++)
			if (v[i].cost > v[j].cost)
				swap(v[i], v[j]);

	unordered_map<int, int>reprezentant;

	for (int i = 1; i <= noduri; i++)
		reprezentant[i] = i;

	int i = 1, nr = 0, cost_total = 0;
	list<pair<int, int>>muchii_afisate;

	do
	{
		if (reprezentant[v[i].st] != reprezentant[v[i].dr])
		{
			nr++;
			//cout << arb[i].st << " " << arb[i].dr << "\n";
			muchii_afisate.push_back(make_pair(v[i].st, v[i].dr));
			cost_total += v[i].cost;
			for (int j = 1; j <= noduri; j++)
				if (reprezentant[j] == reprezentant[v[i].st])
					reprezentant[j] = reprezentant[v[i].dr];
		
		}
		i++;
	} while (nr != noduri - 1);

	o << cost_total << "\n" << noduri - 1 << "\n";

	for (auto it : muchii_afisate)
		o << it.first << " " << it.second << "\n";
}


int main()
{
	int N, M;

	f >> N >> M;

	Graf g(N, M);

	g.apm();
	
	return 0;
}