#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 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<Muchie>* graf;
std::vector<MuchieAPM> muchii_apm;
int* viz;
int* tata;
int n = 0, m = 0, cost_total = 0;

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

	tata[start] = -1;
	viz[start] = 1;
	cost_total = 0;

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

		if(!viz[u.end])
		{
			muchii_apm.push_back(u);
			cost_total += u.cost;
			viz[u.end] = 1;
			tata[u.end] = u.start;

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

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;
	viz = new int[n];
	tata = new int[n];
	graf = new std::vector<Muchie>[n];

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

	std::fill_n(viz, n, 0);
	std::fill_n(tata, n, -1);

	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;
	delete[] viz;
	delete[] tata;
	return 0;
}