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

#define MAXN 200000

struct queue_elem {
  int id, dist, parent;
};

int N, M, heap_size;
int heap_poz[MAXN+1];
queue_elem min_heap[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 smallest, left;
  do {
	  smallest = i;
    left=i<<1;	
    for (int j=left;j<left+2;j++) {
      if (j <= heap_size && min_heap[j].dist < min_heap[smallest].dist) {
		    smallest = j;
	    }
    }
	  if (smallest != i)	{
		  swap(min_heap[i],min_heap[smallest]);
      swap(heap_poz[min_heap[i].id], heap_poz[min_heap[smallest].id]);
		  i = smallest;
	  }
    else break;
  }while(true);
}

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

queue_elem extract_min() {
	queue_elem res = min_heap[1];
	swap(min_heap[1],min_heap[heap_size]);
  swap(heap_poz[min_heap[1].id], heap_poz[min_heap[heap_size].id]);
	heap_size--;
	min_heapify(1);	
	return res;
}

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

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

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