#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX	200000

struct Edge
{
	int in;
	int out;
	int cost;
};

bool compare(Edge a, Edge b)
{
	return a.cost < b.cost;
}

unsigned int n, m;
int sum = 0;
std::vector<Edge> edges;
std::vector<Edge> ansAMA;
int components[MAX];

int findSet ( int node )
{
	if( node == components[node] ) 
	{
		return node;
	}
	else
	{
		return components[node] = findSet(components[node]);
	}
}


void Kruskal()
{
	unsigned int i = 0, numSets = 0;

	while( i < m && numSets < n)
	{
		if ( findSet(edges[i].in) != findSet(edges[i].out) )
		{
			sum += edges[i].cost;
			ansAMA.push_back(edges[i]);
			components[findSet(edges[i].out)] = findSet(edges[i].in);
			++numSets;
		}
		++i;
	}
}

int main()
{
	freopen( "apm.in", "r", stdin );
	freopen( "apm.out", "w", stdout );

	std::cin >> n >> m;
	for( unsigned int i = 0; i < m; ++i )
	{
		Edge e;
		std::cin >> e.in >> e.out >> e.cost;
		edges.push_back(e);
	}

	for( unsigned int i = 1; i <= n; ++i )
		components[i] = i;

	sort(edges.begin(), edges.end(), compare);
	

	Kruskal();
	
	std::cout << sum << "\n" << n - 1 << "\n";
	for( unsigned int i = 0; i < ansAMA.size(); ++i )
	{
		std::cout << ansAMA[i].in <<' ' << ansAMA[i].out << "\n";
	}

	return 0;
}