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

using namespace std;

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

#define MAXN 200000
#define MAXM 400000

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

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

	int auxnod = H[index1];
	H[index1] = H[index2];
	H[index2] = auxnod;
}

void insertKey(int i){ 
    H[heap_size]=i;
	heap_size++; 
    // 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){  
    // Fix the min heap property if it is violated 
	while (i != 0 && C[H[(i-1)/2]] > C[H[i]]) { 
       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 smallest; 
	while(true){
		smallest = i; 
		if ((2*i+1) < heap_size && C[H[2*i+1]] < C[H[i]]) 
			smallest = 2*i+1; 
		if ((2*i+2) < heap_size && C[H[2*i+2]] < C[H[smallest]]) 
			smallest = 2*i+2; 
		if (smallest != i) { 
			swap(i, smallest); 
			i=smallest; 
		}
		else
			break;
	}
} 


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

vector<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;
		C[i]=INFINIT;
		insertKey(i);
		MAP[i]=i;
	}

	int nod,vecin,cost;
	
	extractMin(nod);
	vector<pair<int,int>>::iterator it;

	for(it=L[nod].begin();it!=L[nod].end();it++){
		vecin=it->first;
		cost=it->second;
		C[vecin]=cost;
		E[vecin]=nod;
		decreaseKey(MAP[vecin]);
	}
	outQ[nod]=1;	

	while(heap_size>0){
		extractMin(nod);
		costtotal+=C[nod];

		F[indexF].first=nod;
		F[indexF].second=E[nod];
		indexF++;
		 
		for(it=L[nod].begin();it!=L[nod].end();it++){
			vecin=it->first;
			cost=it->second;
			if(!outQ[vecin] && cost<C[vecin]){
				C[vecin]=cost;
				E[vecin]=nod;
				decreaseKey(MAP[vecin]);
			}
		}
		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;
}