#include<stdio.h>
#include<stdlib.h>

#include<set>
#include<list>
#include<queue>
#include<algorithm>

#include <fstream>
#include <iostream>

using namespace std;

typedef struct elem{
	int nod;
	int cost;
}elem;

#define MAXN 200000
#define MAXM 400000

elem H[2*MAXN-1];
int heap_size;
int MAP[MAXN];

inline void swap(int index1,int index2){
	MAP[H[index1].nod]=index2;
	MAP[H[index2].nod]=index1;

	int auxnod = H[index1].nod;
	int auxcost = H[index1].cost;
	H[index1].nod = H[index2].nod;
	H[index1].cost = H[index2].cost;
	H[index2].nod = auxnod;
	H[index2].cost = auxcost;
}

void insertKey(int k,int cost){ 
    heap_size++; 
    int i = heap_size - 1; 
	H[i].nod = k;
	H[i].cost = cost;
    // Fix the min heap property if it is violated 
	/*
	while (i != 0 && H[(i-1)/2].cost > H[i].cost) { 
       swap((i-1)/2, i); 
       i = (i-1)/2; 
    }
	*/
} 
  
// Decreases value of key at index 'i' to new_val.  It is assumed that 
// new_val is smaller than H[i]. 
void decreaseKey(int i, int new_cost){ 
	H[i].cost = new_cost; 
    // Fix the min heap property if it is violated 
	while (i != 0 && H[(i-1)/2].cost > H[i].cost) { 
       swap((i-1)/2, i); 
       i = (i-1)/2; 
    } 
} 

// A recursive method to heapify a subtree with the root at given index 
// This method assumes that the subtrees are already heapified 
void MinHeapify(int i) { 
	int l,r;
	int smallest; 
	while(true){
		l = 2*i+1; 
		r = 2*i+2; 
		smallest = i; 
		if (l < heap_size && H[l].cost < H[i].cost) 
			smallest = l; 
		if (r < heap_size && H[r].cost < H[smallest].cost) 
			smallest = r; 
		if (smallest != i) { 
			swap(i, smallest); 
			i=smallest; 
		}
		else
			break;
	}
} 


// Method to remove minimum element (or root) from min heap 
void extractMin(int & nod, int & cost) { 
    // Store the minimum value, and remove it from heap 
	cost = H[0].cost;
	nod = H[0].nod;
	
	H[0].nod = H[heap_size-1].nod;
	H[0].cost = H[heap_size-1].cost;
	heap_size--; 
	if(heap_size>1) 
		MinHeapify(0);
} 
  
#define INFINIT 1001
int M,N;

list<pair<int,int>> L[MAXN];
int indexF;
pair<int,int> F[MAXN];

bool outQ[MAXN];
int E[MAXN];

int costtotal;

void arboreprim(){
	for(int i=0;i<N;i++){
		E[i]=-1;
		insertKey(i,INFINIT);
		MAP[i]=i;
	}

	int nod,vecin,cost;
	list<pair<int,int>>::iterator itL;

	extractMin(nod,cost);

	for(itL=L[nod].begin();itL!=L[nod].end();itL++){
		vecin=itL->first;
		cost=itL->second;
		if(cost<H[MAP[vecin]].cost){
			decreaseKey(MAP[vecin],cost);
			E[vecin]=nod;
		}
	}
	outQ[nod]=1;	

	while(heap_size>0){
		extractMin(nod,cost);
		costtotal+=cost;

		F[indexF].first=nod;
		F[indexF].second=E[nod];
		indexF++;
		
		for(itL=L[nod].begin();itL!=L[nod].end();itL++){
			vecin=itL->first;
			cost=itL->second;	
			if(!outQ[vecin] && cost<H[MAP[vecin]].cost){
				decreaseKey(MAP[vecin],cost);
				E[vecin]=nod;
			}
		}
		outQ[nod]=1;	
	}
}

int main(){
		
	freopen("apm.in", "r", stdin);
	//freopen("apm_test7.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d",&N,&M);

	int x,y,c;

	for(int i=0;i<M;i++){
		scanf("%d %d %d",&x,&y,&c);
		L[x-1].push_back(make_pair(y-1,c));
		L[y-1].push_back(make_pair(x-1,c));
	}

	arboreprim();

	printf("%d\n",costtotal);
	printf("%d\n",indexF);

	for(int i=0;i<indexF;i++){
		printf("%d %d\n",F[i].first+1,F[i].second+1);
	}

	return 0;
}