#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, graph_final[200000];
vector < muchie > graph;

class Class_A			  
{
	int rang[100];
	int parent[100];
public:
	Class_A();
	int unionset(int x, int y);
	int link(int x, int y);
	int FindRoot(int x);
};

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

int Class_A::unionset(int x, int y)
{
	return link(parent[x],parent[y]);

}

int Class_A::link(int x, int y)
{
	if (x==y)
		return 0;
	int i;
	if (rang[x] == rang[y])
	{
		parent[x] = y;
		for (i = 0; i < n; i++)
			if (FindRoot(i) == x)
			{
				parent[i] = y;
				rang[i] = 0;
			}
		rang[y] = 1;
	}
	else
	if (rang[x] < rang[y])
	{
		parent[x] = y;
		for (i = 0; i < n; i++)
			if (FindRoot(i) == x)
			{
				parent[i] = y;
				rang[i] = 0;
			}
	}
	else
	{
		parent[y] = x;
		for (i = 0; i < n; i++)
			if (FindRoot(i) == y)
			{
				parent[i] = x;
				rang[i] = 0;
			}
		rang[y] = 0;
	}	
	return 1;
}

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

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


int main()
{
	int i, x, y, c, j;
	f >> n >> m;
	graph.resize(m);
	for (i = 0; i < m; i++)
	{
		f >> x >> y >> c;
		x--;
		y--;
		muchie mch;
		mch.nod1 = x;
		mch.nod2 = y;
		mch.cost = c;
		graph[i] = mch;
	}		   
	Class_A MP;
	sort(graph.begin(), graph.end(), cmp);
	int nr = 0, cost = 0;
	for (i = 0; i < m; i++)
		if(MP.unionset(graph[i].nod1, graph[i].nod2)==1)
		{
			graph_final[nr].nod1 = graph[i].nod1;
			graph_final[nr].nod2 = graph[i].nod2;
			cost += graph[i].cost;
			nr++;

	}
	g << cost << endl << nr << endl;
	for (i = 0; i < nr; i++)
		g << graph_final[i].nod1+1 << " " << graph_final[i].nod2+1 << endl;
	return 0;
}