#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define Inf 1 << 29

FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");

int N,M,x,y,i,cost,D[200005],poz,T[200005],L,Poz[200005],H[400100],COST;

int min(int a,int b){
	if ( a < b )
		return a;
	return b;
}

struct vcn{
	int nod;
	int cst;
}aux;
vector<vcn>A[200005];
vector<vcn>Sol;

void add_apm(int nod){
	vector<vcn>::iterator itt;
	for ( itt = A[nod].begin(); itt != A[nod].end() ; ++itt ){
		aux = *itt;
		D[aux.nod] = min(D[aux.nod],aux.cst);
		if ( D[aux.nod] == aux.cst )
			T[aux.nod] = nod;
	}
}


void coboara ( int x ){
	
	int y = 0;
	while (x != y){
		y = x;
		if (y*2<= L  && D[H[x]]>D[H[y*2]]) x = y*2;
		if (y*2+1<= L && D[H[x]]>D[H[y*2+1]]) x = y*2+1;
		swap(H[x],H[y]);
		swap(Poz[H[x]],Poz[H[y]]);
	}
}

void urca(int poz){
	while ( poz > 1 && D[H[poz]] < D[H[poz/2]] ) {
		swap(H[poz],H[poz/2]);
		swap(Poz[H[poz]],Poz[H[poz/2]]);
		poz /= 2;
	}
	
}


void add_heap(int nod){
	H[++L] = nod;
	Poz[nod] = L;
	
	urca(L);
	
}


int minusroot() {
	int x = H[1];
	swap(H[1],H[L]);
	swap(Poz[H[1]],Poz[H[L]]);
	--L;
	coboara(1);
	Poz[x] = 0;
	return x;
	
}

int main () {
	fscanf(f,"%d %d",&N,&M);
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&cost);
		aux.nod = y; aux.cst = cost;
		A[x].push_back(aux);
		aux.nod = x; aux.cst = cost;
		A[y].push_back(aux);
	}
	
	for ( i = 2 ; i <= N ; ++i )	D[i] = Inf;
	
	add_apm(1);
	for ( i = 2 ; i <= N ; ++i )
		add_heap(i);
	
	vector<vcn>::iterator itt;
	for ( i = 1 ; i < N ; ++i ){
		int nd = minusroot();
		
		add_apm(nd);
		
		COST += D[nd];
		
		aux.nod = nd; aux.cst = T[nd];
		Sol.push_back(aux);
		
		
		for ( itt = A[nd].begin(); itt != A[nd].end(); ++itt ){
			aux = *itt;
			if ( Poz[aux.nod] )
				urca(Poz[aux.nod]);
		}
		
		
	}
	fprintf(g,"%d\n%d\n",COST,N-1);
	
	for ( itt = Sol.begin(); itt != Sol.end() ; ++itt ){
		aux = *itt;
		fprintf(g,"%d %d\n",aux.nod,aux.cst);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}