#include <cstdio>

const unsigned int MAX_VERTICES(200000);
const signed short MAX_COST(1001);

struct vertex
{
	unsigned int number;
	signed int cost;
};

struct linked_list_element
{
	struct vertex data;
	struct linked_list_element *next;
};

struct linked_list_element *graph[MAX_VERTICES];
unsigned int pred [MAX_VERTICES];
unsigned int min_heap [MAX_VERTICES];
unsigned int heap_index [MAX_VERTICES];
signed short cost [MAX_VERTICES];

inline void heap_up (unsigned int index)
{
	if (index > 1)
	{
		unsigned int father(index >> 1), vertex(min_heap[index]), father_vertex(min_heap[father]);
		signed int vertex_cost(cost[vertex]);
		while (vertex_cost < cost[father_vertex])
		{
			heap_index[vertex] ^= heap_index[father_vertex];
			heap_index[father_vertex] ^= heap_index[vertex];
			heap_index[vertex] ^= heap_index[father_vertex];
			min_heap[index] = father_vertex;
			index = father;
			if (index > 1)
			{
				father >>= 1;
				father_vertex = min_heap[father];
			}
			else
				break;
		}
		min_heap[index] = vertex;
	}
}

inline void heap_down (unsigned int index)
{
	unsigned int left(index << 1), right(left + 1), smallest, vertex(min_heap[index]), heap_size(*min_heap), smallest_vertex;
	while (true)
	{
		if (left < heap_size && cost[min_heap[left]] < cost[vertex])
			smallest = left;
		else
			smallest = index;
		if (right < heap_size && cost[min_heap[right]] < cost[min_heap[smallest]])
			smallest = right;
		if (smallest == index)
			break;
		smallest_vertex = min_heap[smallest];
		heap_index[vertex] ^= heap_index[smallest_vertex];
		heap_index[smallest_vertex] ^= heap_index[vertex];
		heap_index[vertex] ^= heap_index[smallest_vertex];
		min_heap[index] ^= min_heap[smallest];
		min_heap[smallest] ^= min_heap[index];
		min_heap[index] ^= min_heap[smallest];
		index = smallest;
		vertex = min_heap[index];
		left = index << 1;
		right = left + 1;
	}
}

void pop (void)
{
	--*min_heap;
	min_heap[1] = min_heap[*min_heap];
	heap_index[min_heap[1]] = 1;
	heap_down(1);
}

signed int Prim (void)
{
	for (unsigned int initializer(1), size(*min_heap) ; initializer < size ; ++initializer)
	{
		min_heap[initializer] = heap_index[initializer] = initializer;
		cost[initializer] = MAX_COST;
	}
	cost[1] = 0;
	unsigned int vertex, neighbor;
	signed short new_cost;
	signed int total_cost(0);
	struct linked_list_element *iterator;
	do
	{
		vertex = min_heap[1];
		pop();
		for (iterator = graph[vertex] ; iterator ; iterator = iterator->next)
		{
			neighbor = iterator->data.number;
			if (heap_index[neighbor] > 1 || min_heap[1] == neighbor)
			{
				new_cost = iterator->data.cost;
				if (new_cost < cost[neighbor])
				{
					cost[neighbor] = new_cost;
					pred[neighbor] = vertex;
					heap_up(heap_index[neighbor]);
				}
			}
		}
		total_cost += cost[vertex];
	}
	while (*min_heap > 1);
	return total_cost;
}

int main (void)
{
	std::freopen("apm.in","r",stdin);
	unsigned int n,m;
	std::scanf("%u%u",&n,&m);
	struct linked_list_element *new_element;
	unsigned int node1, node2, *node1_ptr(&node1), *node2_ptr(&node2);
	signed int cost, *cost_ptr(&cost);
	do
	{
		std::scanf("%u%u%d",node1_ptr,node2_ptr,cost_ptr);
		new_element = new struct linked_list_element;
		new_element->data.number = node2;
		new_element->data.cost = cost;
		new_element->next = graph[node1];
		graph[node1] = new_element;
		new_element = new struct linked_list_element;
		new_element->data.number = node1;
		new_element->data.cost = cost;
		new_element->next = graph[node2];
		graph[node2] = new_element;
		--m;
	}
	while (m);
	std::fclose(stdin);
	*min_heap = n + 1;
	cost = Prim();
	std::freopen("apm.out","w",stdout);
	std::printf("%d\n%d\n",cost,n - 1);
	do
	{
		std::printf("%u %u\n",pred[n],n);
		--n;
	}
	while (n > 1);
	std::fclose(stdout);
	return 0;
}