#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <set>
using namespace std;

int N, M;

struct link
{
	int source;
	int destination;
	int cost;
	link(int source, int destination,int cost): source(source),destination(destination), cost(cost) {}
};
struct CompareLink
{
	int operator()(const link & a, const link & b)
	{
		return a.cost > b.cost;
	}
};

struct nod
{
	//int myIndex;
	// All the links to all the neighbours
	vector<link> links;

	void addLink(int source, int destination, int cost)
	{
		links.push_back(link(source, destination, cost));
	}

	nod()
	{
		//cout << "Created node";
	}
};

void addConnections(nod& node, priority_queue<link, vector<link>, CompareLink>& connections)
{

}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	// Program
	f >> N >> M;
	vector<nod> nodes(N + 1, nod());
	for (int i = 0; i < M; i++)
	{
		int source, destination, cost;
		f >> source >> destination >> cost;
		nodes[source].addLink(source, destination, cost);
		nodes[destination].addLink(destination, source, cost);
	}

	vector<bool> inTree(N + 1);
	priority_queue<link, vector<link>, CompareLink> connections;

	//inTree[1] = true;
	for (auto it = nodes[1].links.begin(); it != nodes[1].links.end(); it++)
	{
		connections.push(*it);
	}
	inTree[1] = true;

	int total = 0;
	vector<link> sol;

	while (sol.size() < N-1)
	{
		link l = connections.top();
		connections.pop();

		if (inTree[l.destination])
		{
			continue;
		}
		inTree[l.source] = true;
		inTree[l.destination] = true;

		total += l.cost;
		sol.push_back(l);

		for (auto it = nodes[l.destination].links.begin(); it != nodes[l.destination].links.end(); it++)
		{
			if (!inTree[it->destination])
			{
				connections.push(*it);
			}
		}

	}

	g << total << endl;
	g << N - 1 << endl;
	for (auto it = sol.begin(); it != sol.end(); it++)
	{
		g << it->source << " " << it->destination << endl;
	}


	// Exit
	f.close();
	g.close();
	return 0;
}