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

#define MAXN 200001
#define MAXM 400001

struct vertice{
	int left;
	int right;
	int cost;
};

struct compare
{
      bool operator()(const vertice &A, const vertice &B)
      {
        return A.cost > B.cost;
      }
};

bool taken[MAXN];
std::vector<vertice> v[MAXN];
std::vector<vertice> solutie;
std::priority_queue<vertice,std::vector<vertice>,compare> heap;

int N,M;

int main(int argc, char* argv[])
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	int i;
	vertice aux;
	vertice start;
	start.cost = 0x7FFFFFFF;
	
	for(i=0;i<M;i++){
		scanf("%d %d %d",&aux.left,&aux.right,&aux.cost);
		v[aux.left].push_back(aux);
		v[aux.right].push_back(aux);
		
		if( aux.cost < start.cost ){
			start = aux;
		}
	}
	
	taken[start.left] = true;
	taken[start.right] = true;
	solutie.push_back(start);
	std::vector<vertice>::iterator it;
	for(it = v[start.left].begin(); it != v[start.left].end(); it++){
		if( !taken[it->left] || !taken[it->right] ){
			heap.push(*it);
		}
	}
	for(it = v[start.right].begin(); it != v[start.right].end(); it++){
		if( !taken[it->left] || !taken[it->right] ){
			heap.push(*it);
		}
	}
	
	
	
	int muchios=N-2;
	int sum = start.cost;
	while(muchios > 0 ){
		start = heap.top();
		heap.pop();
		
		if( !taken[start.left] ){
			solutie.push_back(start);
			sum  += start.cost;
			taken[start.left] = true;
			for(it = v[start.left].begin(); it != v[start.left].end(); it++){
				if( !taken[it->left] || !taken[it->right] ){
					heap.push(*it);
				}
			}
			muchios--;		
		}
		else if( !taken[start.right] ){
			solutie.push_back(start);
			sum += start.cost;
			taken[start.right] = true;
			for(it = v[start.right].begin(); it != v[start.right].end(); it++){
				if( !taken[it->left] || !taken[it->right] ){
					heap.push(*it);
				}
			}
			muchios--;
		}		
	}	
	
	printf("%d\n%d\n",sum,N-1);
	for(it=solutie.begin();it != solutie.end();it++){
		printf("%d %d\n",it->left,it->right);
	}
	
	return 0;
}