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

#define MAXN 200000

int N, M, heap_size;
int min_heap[MAXN+1], heap_poz[MAXN+1], bestDist[MAXN+1], parent[MAXN+1];
list<pair<int, int> > adj_list[MAXN+1], 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, left=i<<1, 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]);
		swap(heap_poz[min_heap[i]], heap_poz[min_heap[smallest]]);
		min_heapify(smallest,size);
	}
}

void init_all() {
	for (int i=1;i<=N;i++) {
		min_heap[i] = heap_poz[i] = i;
		bestDist[i] = INT_MAX;
		parent[i] = -1;
	}
	bestDist[1] = 0;
	heap_size = N;
}

int extract_min() {
	swap(min_heap[1],min_heap[heap_size]);
	heap_poz[min_heap[1]] = 1;
	heap_poz[min_heap[heap_size]] = 0;
	heap_size--;
	min_heapify(1,heap_size);
	return min_heap[heap_size+1];
}

void decrease_key(int poz) {
	int parent = poz>>1;
	while (parent > 0 && bestDist[min_heap[poz]] < bestDist[min_heap[parent]]) {
		swap(min_heap[poz],min_heap[parent]);
		swap(heap_poz[min_heap[poz]],heap_poz[min_heap[parent]]);
		poz = parent;
		parent = poz>>1;
	}
}

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

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

	solution.pop_front();
	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;
}