#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct muchie{
	int x, y, c;
};
bool comp(muchie a, muchie b){
	return a.c < b.c;
}
vector <pair <int, int>> ras;
vector <muchie> v;
int rad[200005];
static inline int find(int x){
	if( rad[x] < 0 ){
		return x;
	}
	rad[x] = find( rad[x] );
	return rad[x];
}
static inline void unite(int x, int y){
	if( rad[x] > rad[y] ){
		swap( x, y );
	}
	rad[x] += rad[y];
	rad[y] = x;
}
int main(){
	int n, m, i, x, y, cost_total, c, rad_x, rad_y;
	ifstream fin( "apm.in" );
	ofstream fout( "apm.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y >> c;
		v.push_back( { x, y, c } );
	}
	sort( v.begin(), v.end(), comp );
	for( i = 1; i <= n; i++ ){
		rad[i] = -1;
	}
	cost_total = 0;
	for( i = 0; i < m; i++ ){
		x = v[i].x;
		y = v[i].y;
		c = v[i].c;
		rad_x = find( x );
		rad_y = find( y );
		if( rad_x != rad_y ){
			unite( rad_x, rad_y );
			ras.push_back( { x, y } );
			cost_total += c;
		}
	}
	fout << cost_total << '\n' << ras.size() << '\n';
	for( i = 0; i < ras.size(); i++ ){
		fout << ras[i].first << ' ' << ras[i].second << '\n';
	}
	return 0;
}