#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <utility>
#include <limits>

typedef std::pair<unsigned int, signed int> vertex;
typedef std::list<vertex> edge;
typedef std::vector<edge> graph;

template <typename T>
class min_heap
{
	public :
		min_heap (const unsigned int __SIZE) : size(__SIZE), queue(__SIZE), cost(__SIZE,std::numeric_limits<T>::max()), queue_index(__SIZE)
		{
			cost[0] = 0;
			for (unsigned int initializer(0) ; initializer < __SIZE ; ++initializer)
				queue_index[initializer] = queue[initializer] = initializer;
		}
		// Default copy constructor
		// Default assignment operator
		// Default destructor
		void pop (void);
		unsigned int top (void);
		bool enqued (const unsigned int vertex);
		void adjust_up (const unsigned int vertex, const T new_cost);
		friend signed int Prim (graph &g, std::vector<unsigned int> &pred);
	private :
		unsigned int size;
		std::vector<unsigned int> queue;
		std::vector<T> cost;
		std::vector<unsigned int> queue_index;
	private :
		void up (unsigned int index);
		void down (unsigned int index);
};

template <typename T>
inline void min_heap<T>::up (unsigned int index)
{
	unsigned int father((index - 1) >> 1), vertex(queue[index]), father_vertex(queue[father]);
	T vertex_cost(cost[vertex]);
	while (vertex_cost < cost[father_vertex])
	{
		std::swap(queue_index[vertex],queue_index[father_vertex]);
		queue[index] = father_vertex;
		index = father;
		if (index)
		{
			--father;
			father >>= 1;
			father_vertex = queue[father];
		}
		else
			break;
	}
	queue[index] = vertex;
}

template <typename T>
inline void min_heap<T>::down (unsigned int index)
{
	unsigned int left((index << 1) + 1), right(left + 1), smallest, vertex(queue[index]);
	while (true)
	{
		if (left < size && cost[queue[left]] < cost[vertex])
			smallest = left;
		else
			smallest = index;
		if (right < size && cost[queue[right]] < cost[queue[smallest]])
			smallest = right;
		if (smallest == index)
			break;
		std::swap(queue_index[vertex],queue_index[queue[smallest]]);
		std::swap(queue[index],queue[smallest]);
		index = smallest;
		vertex = queue[index];
		left = (index << 1) + 1;
		right =  left + 1;
	}
}

template <typename T>
inline void min_heap<T>::pop (void)
{
	--size;
	queue[0] = queue[size];
	queue.pop_back();
	queue_index[queue[0]] = 0;
	down(0);
}

template <typename T>
inline unsigned int min_heap<T>::top (void)
{
	return queue[0];
}

template <typename T>
inline bool min_heap<T>::enqued (const unsigned int vertex)
{
	return queue_index[vertex] || queue[0] == vertex;
}

template <typename T>
inline void min_heap<T>::adjust_up (const unsigned int vertex, const T new_cost)
{
	cost[vertex] = new_cost;
	unsigned int index(queue_index[vertex]);
	if (index)
		up(index);
}

signed int Prim (graph &g, std::vector<unsigned int> &pred)
{
	unsigned int size(g.size());
	class min_heap<signed int> pq(size);
	unsigned int vertex, neighbor;
	signed int minimum_cost(0), new_cost;
	edge::const_iterator iterator, end;
	do
	{
		vertex = pq.top();
		pq.pop();
		for (iterator = g[vertex].begin(), end = g[vertex].end() ; iterator != end ; ++iterator)
		{
			neighbor = iterator->first;
			if (pq.enqued(neighbor))
			{
				new_cost = iterator->second;
				if (new_cost < pq.cost[neighbor])
				{
					pred[neighbor] = vertex;
					pq.adjust_up(neighbor,new_cost);
				}
			}
		}
		minimum_cost += pq.cost[vertex];
	}
	while (pq.size);
	return minimum_cost;
}

int main (void)
{
	unsigned int n,m;
	std::ifstream input("apm.in");
	input >> n >> m;
	unsigned int from_node, to_node;
	signed int cost;
	graph g(n);
	do
	{
		input >> from_node >> to_node >> cost;
		--from_node;
		--to_node;
		g[from_node].push_front(std::make_pair(to_node,cost));
		g[to_node].push_front(std::make_pair(from_node,cost));
		--m;
	}
	while (m);
	input.close();
	std::vector<unsigned int> pred(n);
	signed int minimum_spaning_tree_cost(Prim(g,pred));
	--n;
	std::ofstream output("apm.out");
	output << minimum_spaning_tree_cost << '\n' << n << '\n';
	do
	{
		output << pred[n] + 1 << ' ' << n + 1 << '\n';
		--n;
	}
	while (n);
	return 0;
}