// Infoarena - Arhiva Educationala APM
// Februrie 2012 Marius Dumitran
// implementare clasica O(M * log*N)

#include<string.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#define maxn 200001
#define maxm 400001

using namespace std;

struct muchie{ 
	int a, b, c;
};
bool cmp_fnc( const muchie &a1, const muchie &b1) {
	return (a1.c < b1.c);
}

muchie muc[maxm];
int tata[ maxn ], size[ maxn ];



void arhive(int nod) {
	int temp_nod = nod;
	while (tata[ temp_nod ] != temp_nod)
		temp_nod = tata[ temp_nod ];
	int tati = temp_nod;
	while (tata[ nod ] != nod)  {
		temp_nod = tata[ nod ];
		tata[ nod ] = tati;
		nod = temp_nod;
	}
}

int join( int nod1, int nod2) {
	arhive (nod1);
	arhive (nod2);
	int tata1 = tata[nod1], tata2 = tata[nod2];
	if( tata1 == tata2) return 0;
	if( size[ tata1 ] > size[tata2] )
		tata1 = tata1 ^ tata2 ^(tata2 = tata1);
	size[ tata2 ] += size[ tata1 ];
	tata[ tata1 ] = tata2;
	return 1;
}


int main(){
	
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	for( int i = 1; i <= n; ++i) 
		tata[i] = i, size[i] = 1;
	for( int i = 0; i < m; ++i) 
		scanf("%d %d %d", &muc[i].a, &muc[i].b, &muc[i].c);
	
	sort( muc, muc + m, cmp_fnc);
	vector < int> sol; int val = 0;
	for( int i = 0; i < m; ++i) {
		if( join(muc[i].a, muc[i].b)) {
			sol.push_back(i);
			val += muc[i].c;
		}
	}
	printf("%d\n%d\n", val, sol.size());
	for( int i = 0; i < sol.size(); ++i) {
		printf("%d %d\n", muc[sol[i]].a, muc[sol[i]].b);
	}
	
	return 0;
	
}