#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct triplet{
	int x, y, c;
};

vector<triplet> E;
vector<int> t, h;
vector<triplet> APCM;

bool cmp( triplet x, triplet y )
{
	if ( x.c < y.c )
		return true;
	return false;
}

int find( int x )
{
	if ( t[x] == 0 )
		return x;
	return find(t[x]);
}

void myunion( int x, int y )
{
	int tx = find(x);
	int ty = find(y);
	if ( tx == ty )
		return;
	if ( h[x] > h[y] )
	{
		t[ty] = tx;
		return;
	}
	if( h[x] < h[y] )
	{
		t[tx] = ty;
		return;
	}
	t[tx] = ty;
	h[tx]++;
}

int main()
{
	int n, m;
	ifstream in("apm.in");
	in >> n >> m;
	E.resize(m);
	t.resize(n+1);
	h.resize(n+1);
	for( int i = 0; i <m ;i++ )
	{
		in >> E[i].x >> E[i].y >> E[i].c;
	}
	
	sort(E.begin(),E.end(), cmp);

	int cost = 0;
	for ( int i = 0; i < m; i++ )
	{
		triplet muchie = E[i];
		if ( find(muchie.x) != find(muchie.y) )
		{		
			myunion(muchie.x, muchie.y);
			APCM.push_back(muchie);
			cost+=muchie.c;
		}
	}
	ofstream out("apm.out");
	out << cost<<'\n';
	out << APCM.size()<<'\n';
	for ( int i = 0; i < APCM.size(); i++ )
	{
		out<<APCM[i].x<<' '<<APCM[i].y<<'\n';
	}
	in.close();
	out.close();
	return 0;
}