#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>


using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
struct muchie
{
	int nod1, nod2, cost;
}mch;
vector < muchie > graph;

class Class_A			  
{
	vector<int> rang;
	vector<int> parent;
public:
	Class_A();
	void unionset(int x, int y);
	void link(int x, int y);
	int FindRoot(int x);
};

Class_A::Class_A()
{
	int i;
	rang.resize(n+1,0);
	parent.resize(n+1);
	for (i = 0; i <= n; i++)
	{				 
		parent[i] = i;
	}
}

void Class_A::unionset(int x, int y)
{
	link(FindRoot(x),FindRoot(y));

}

void Class_A::link(int x, int y)
{
	if (rang[x] < rang[y]) 
		parent[x] = y;
	else 
	{
		if (rang[x] > rang[y]) 
			parent[y] = x;
		else 
		{
			parent[x] = y;
			rang[y]++;
		}
	}
}

int Class_A::FindRoot(int x)
{
	int i, aux;
	for (i = x; parent[i] != i; i = parent[i]) 
	{

	}
	while (parent[x] != x) 
	{
		aux = parent[x];
		parent[x] = i;
		x = aux;
		rang[i]--;
	}
	return i;
}

int cmp(muchie a, muchie b)
{
	return (a.cost < b.cost);
}


int main()
{
	int i, x, y, c, j;
	f >> n >> m;
	for (i = 0; i < m; i++)
	{
		f >> x >> y >> c;
		muchie mch;
		mch.nod1 = x;
		mch.nod2 = y;
		mch.cost = c;
		graph.push_back(mch);
	}		   
	Class_A MP;
	sort(graph.begin(), graph.end(), cmp);
	int costTot = 0;
	vector<pair <int, int> > graph_final;
	for (i = 0; i < graph.size(); i++) 
	{
		x = graph[i].nod1;
		y = graph[i].nod2;
		c = graph[i].cost;

		if (MP.FindRoot(x) != MP.FindRoot(y)) 
		{
			graph_final.push_back(make_pair(x, y));
			MP.unionset(x, y);
			costTot += c;
		}
	}
	
	g << costTot << endl << graph_final.size() << endl;
	for (i = 0; i < graph_final.size(); i++)
		g << graph_final[i].first << " " << graph_final[i].second << endl;
	return 0;
}