#include<fstream>
#include<algorithm>

using namespace std;

#define max_n 200010
#define max_m 400010

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
	int x , y , c;
}M[max_n];

int Sol[max_n] , n , m , V[max_n] , nr_muchii , cost , k = 1;

bool cmp( muchie a , muchie b ){
	return a.c < b.c;
}

void read(){

	f>>n>>m;

	for( int i = 1 ; i <= m ; i++ ){
		f>>M[i].x>>M[i].y>>M[i].c;
	}

	sort( M + 1 , M + m + 1 , cmp );

}

void init(){

	for( int i = 1 ; i <= n ; i++ )
		V[i] = -1;

}

int rad( int x ){

	while( V[x] > 0 )
		x = V[x];
	return x;

}

void merge( int x , int y ){

	int tx = rad(x) , ty = rad(y);

	if( V[tx] < V[ty] ){
		V[tx] += V[ty];
		V[ty] = tx;
	}
	else{
		V[ty] += V[tx];
		V[tx] = ty;
	}

}

int main(){

	read();

	init();

	while( nr_muchii != (n-1) ){
		if( rad( M[k].x ) != rad( M[k].y ) ){
			merge( M[k].x , M[k].y );
			Sol[++nr_muchii] = k;
			cost += M[k].c;
		}
		k++;
	}

	g<<cost<<"\n"<<n-1<<"\n";

	for( int i = 1 ; i < n ; i++ )
		g<<M[Sol[i]].x<<" "<<M[Sol[i]].y<<"\n";

	return 0;
}