#include <cstdio>
#include <list>
#include <climits>
using namespace std;

#define MAXN 200000
#define MAXM 400000

struct edge {
	int from;
	int to;
	int cost;
};

int N, M, heap_size;
int bestDist[MAXN+1];
bool inAPM[MAXN+1];
int parent[MAXN+1];
int min_heap[MAXN];
list<pair<int, int> > adj_list[MAXN+1];
list<pair<int, int> > solution;

void readInput() {	
	int from, to, cost;
	freopen("apm.in","r",stdin);
	scanf("%d %d",&N,&M);
	for (int i=1;i<=M;i++) {
		scanf("%d %d %d",&from,&to,&cost);
		adj_list[from].push_back(make_pair(to,cost));
		adj_list[to].push_back(make_pair(from,cost));
	}
}

void min_heapify(int i, int size)
{
	int smallest = i;
	int left = i << 1;
	int right = left+1;
	if (left <= size && bestDist[min_heap[left]] < bestDist[min_heap[smallest]])	{
		smallest = left;
	}
	if (right <= size && bestDist[min_heap[left]] < bestDist[min_heap[smallest]])	{
		smallest = right;
	}
	if (smallest != i)	{
		swap(min_heap[i],min_heap[smallest]);
		min_heapify(smallest,size);
	}
}

void build_min_heap()
{
	for (int i = (N-1)/2;i>0;i--) {
		min_heapify(i,N-1);
	}
	heap_size = N-1;
}

int extract_min()
{
	if (heap_size>0) {
		swap(min_heap[1],min_heap[heap_size]);
		heap_size--;
		min_heapify(1,heap_size);
		return min_heap[heap_size+1];
	}
	return INT_MAX;
}

int main()
{
	int i, tree_cost = 0;
	readInput();

	for (i=1;i<=N;i++) {
		bestDist[i] = INT_MAX;
		parent[i] = -1;
	}
	bestDist[1] = 0;
	inAPM[1] = true;
	for (list<pair<int, int> >::iterator it=adj_list[1].begin();it!=adj_list[1].end();it++) {
		bestDist[((pair<int, int>)*it).first] = ((pair<int, int>)*it).second;
		parent[((pair<int, int>)*it).first] = 1;
	}

	for (i=1;i<N;i++) {
		min_heap[i] = i+1;
	}
	build_min_heap();

	while (heap_size > 0) {
		int u = extract_min();
		tree_cost += bestDist[u];
		solution.push_back(make_pair(parent[u],u));
		inAPM[u] = true;
		for (list<pair<int, int> >::iterator it=adj_list[u].begin();it!=adj_list[u].end();it++) {
			int v = ((pair<int, int>)*it).first;
			int cost = ((pair<int, int>)*it).second;
			if (!inAPM[v] && bestDist[v] > cost) {
				bestDist[v] = cost;
				parent[v] = u;
			}
		}
	}

	freopen("apm.out","w",stdout);
	printf("%d\n%d\n",tree_cost,solution.size());
	for (list<pair<int, int> >::iterator it=solution.begin();it!=solution.end();it++) {
		printf("%d %d\n",((pair<int, int>)*it).first, ((pair<int, int>)*it).second);
	}
	return 0;
}