#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

struct Muchie {
	int nod, cost;
	Muchie(int nod = 0, int cost = 0) : nod(nod), cost(cost) {}
};

struct Varf {
	bool viz;
	std::vector<Muchie> muchii;
	Varf() : viz(false), muchii() {}
};

struct MuchieAPM {
	int start, end, cost;
	MuchieAPM(int start = 0, int end = 0, int cost = 0) : start(start), end(end), cost(cost) {}
};

struct MuchieAPMCompare {
	bool operator() (const MuchieAPM& lhs, const MuchieAPM& rhs) const {
		return lhs.cost > rhs.cost;
	}
};

std::priority_queue<MuchieAPM, std::vector<MuchieAPM>, MuchieAPMCompare> pq;
std::vector<MuchieAPM> muchii_apm;
Varf* graf;
int n = 0, m = 0, cost_total = 0;

void prim(int start)
{
	for(size_t i = 0; i < graf[start].muchii.size(); i++)
		pq.push(MuchieAPM(start, graf[start].muchii[i].nod, graf[start].muchii[i].cost));

	graf[start].viz = 1;
	cost_total = 0;

	while(!pq.empty())
	{
		MuchieAPM u = pq.top();
		pq.pop();

		if(!graf[u.end].viz)
		{
			muchii_apm.push_back(u);
			cost_total += u.cost;
			graf[u.end].viz = true;

			for(size_t i = 0; i < graf[u.end].muchii.size(); i++)
			{
				int v = graf[u.end].muchii[i].nod;
				int c = graf[u.end].muchii[i].cost;
				if(!graf[v].viz)
				{
					pq.push(MuchieAPM(u.end, v, c));
				}
			}
		}
	}
}

int main()
{
	std::ifstream fin("apm.in");
	std::ofstream fout("apm.out");
	if(!fin.is_open() || !fout.is_open())
		return -1;

	int a = 0, b = 0, c = 0;

	fin >> n >> m;
	graf = new Varf[n];

	for(int i = 0; i < m; i++)
	{
		fin >> a >> b >> c;
		graf[a - 1].muchii.push_back(Muchie(b - 1, c));
		graf[b - 1].muchii.push_back(Muchie(a - 1, c));
	}

	prim(0);

	fout << cost_total << '\n';
	fout << muchii_apm.size() << '\n';

	for(size_t i = 0; i < muchii_apm.size(); i++)
		fout << muchii_apm[i].start + 1 << ' ' << muchii_apm[i].end + 1 << '\n';

	delete[] graf;
	return 0;
}