#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 200100
typedef vector<int> vi;
struct muchie { 
	int x, y, c; 
	muchie(int _x, int _y, int _c){ x=_x, y=_y, c=_c; }
};
typedef vector<muchie> vm;
typedef vector<bool> vb;
int cmp( muchie A, muchie B ) { return A.c < B.c; } 

vm Muchii;
vi T, H;
vb B;
int M,N,CT;

void load() { 
	freopen( "apm.in", "r", stdin );
	freopen( "apm.out", "w", stdout );

	scanf("%d %d", &N, &M);
	for ( int i=0; i<M; ++i ) {
		int x, y, c;
		scanf("%d %d %d", &x, &y, &c);
		Muchii.push_back( muchie(x,y,c) );
		Muchii.push_back( muchie(y,x,c) );
	}
}

int Tata( int x ) { return (T[x]==x)? x : Tata(T[x]); }
void Reuneste( int x, int y ) {
	int tx = Tata(x), ty = Tata(y);
	if ( H[tx] == H[ty] ) {
		H[tx] ++;
		T[ty] = tx;
	} else {
		if ( H[tx] < H[ty] ) 
			T[tx] = ty;
		else
			T[ty] = tx;
	}
}

void kruskal() {
	T.resize( N+1 ); H.resize( N+1 );
	for ( int i=1; i<=N; ++i )
		T[i] = i, H[i] = 0;
	sort( Muchii.begin(), Muchii.end(), cmp );
	for ( vm::iterator it = Muchii.begin(); it!=Muchii.end(); ++it ) {
		int x = it->x, y = it->y, c = it->c;
		if ( Tata(x) != Tata(y) ) {
			Reuneste(x,y);
			B.push_back(true);
			CT += c;
		} else
			B.push_back(false);
	}
}

void output() {
	int i, nr = 0;
	vm::iterator it;
	for ( vb::iterator ib=B.begin(); ib!=B.end(); ++ib ) 
		if ( *ib ) ++nr;
	printf("%d\n%d\n", CT, nr);
	for ( i=0, it = Muchii.begin(); it!=Muchii.end(); ++it, ++i )
		if ( B[i] ) 
			printf("%d %d\n", it->x, it->y);
}

int main() {
	load();
	kruskal();
	output();
	return 0;
}