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

#define MAXN 200000

int N, M, heap_size;
int bestDist[MAXN+1];
bool inAPM[MAXN+1];
int parent[MAXN+1];
int min_heap[MAXN];
int heap_poz[MAXN+1];
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]);
		heap_poz[min_heap[i]]=i;
		heap_poz[min_heap[smallest]]=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_poz[min_heap[1]]=1;
		heap_size--;
		min_heapify(1,heap_size);
		return min_heap[heap_size+1];
	}
	return INT_MAX;
}

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]);
		heap_poz[min_heap[poz]] = poz;
		heap_poz[min_heap[parent]] = parent;
		poz = parent;
		parent = poz>>1;
	}
}

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;
		heap_poz[i+1] = i;
	}
	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;
				decrease_key(heap_poz[v]);
			}
		}
	}

	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;
}