// Kruskal's algorithm

#include <cstdio>

const int MAX_V(200001);
const int MAX_E(400001);

int v, e, mst_cost;

int forest [MAX_V];

inline void init_forest (void)
{
	for (int *iterator(forest + 1), *end(forest + v) ; iterator <= end ; ++iterator)
		*iterator = -1;
}

int find (int x)
{
	if (forest[x] < 0)
		return x;
	forest[x] = find(forest[x]);
	return forest[x];
}

inline void merge (int x, int y)
{
	x = find(x);
	y = find(y);
	if (forest[y] < forest[x])
	{
		x ^= y;
		y ^= x;
		x ^= y;
	}
	forest[x] += forest[y];
	forest[y] = x;
}

struct edge
{
	int x;
	int y;
	int cost;
} heap [MAX_E];
int heap_size;

inline void operator ^= (struct edge &a, struct edge &b)
{
	a.x ^= b.x;
	a.y ^= b.y;
	a.cost ^= b.cost;
}

inline void heap_up (void)
{
	if (heap_size > 1)
	{
		int father((heap_size - 1) >> 1), index(heap_size);
		const struct edge VALUE(heap[index]);
		const int COST(VALUE.cost);
		while (COST < heap[father].cost)
		{
			heap[index] = heap[father];
			index = father;
			if (father)
			{
				--father;
				father >>= 1;
			}
			else
				break;
		}
		heap[index] = VALUE;
	}
}

inline void push (int x, int y, int cost)
{
	heap[heap_size].x = x;
	heap[heap_size].y = y;
	heap[heap_size].cost = cost;
	heap_up();
	++heap_size;
}

inline void heap_down (void)
{
	int index(0), left(1), right(2), smallest;
	while (true)
	{
		if (left < heap_size && heap[left].cost < heap[index].cost)
			smallest = left;
		else
			smallest = index;
		if (right < heap_size && heap[right].cost < heap[smallest].cost)
			smallest = right;
		if (smallest == index)
			break;
		heap[smallest] ^= heap[index];
		heap[index] ^= heap[smallest];
		heap[smallest] ^= heap[index];
		index = smallest;
		left = (index << 1) + 1;
		right = left + 1;
	}
}

inline void pop (void)
{
	if (heap_size)
	{
		--heap_size;
		*heap = heap[heap_size];
		heap_down();
	}
}

struct tree
{
	int x;
	int y;
} mst [MAX_E], *add_edge(mst);

inline void read (void)
{
	std::freopen("apm.in","r",stdin);
	std::scanf("%d%d",&v,&e);
	int edges(e), x, *x_ptr(&x), y, *y_ptr(&y), cost, *cost_ptr(&cost);
	do
	{
		std::scanf("%d%d%d",x_ptr,y_ptr,cost_ptr);
		push(x,y,cost);
		--edges;
	}
	while (edges);
	std::fclose(stdin);
}

inline void Kruskal (void)
{
	init_forest();
	int x, y;
	struct tree *mst_end(mst + v - 1);
	while (add_edge < mst_end)
	{
		while (find(heap->x) == find(heap->y))
			pop();
		x = heap->x;
		y = heap->y;
		mst_cost += heap->cost;
		pop();
		merge(x,y);
		add_edge->x = x;
		add_edge->y = y;
		++add_edge;
	}
}

inline void print (void)
{
	std::freopen("apm.out","w",stdout);
	std::printf("%d\n%d\n",mst_cost,v - 1);
	for (struct tree *iterator(mst), *end(add_edge) ; iterator < end ; ++iterator)
		std::printf("%d %d\n",iterator->x,iterator->y);
	std::fclose(stdout);
}

int main (void)
{
	read();
	Kruskal();
	print();
	return 0;
}