#include <iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>
#include <math.h>
using namespace std;

struct muchie {

	int u, v;
	long long cost;
	bool ama;
};

struct subm {
	int parinte; /*radacina*/
	int h; /*h ,"height" */

	subm()
	{
		parinte = 0;
		h = 0;
	}
};


bool operator<(muchie a, muchie b)
{
	return a.cost < b.cost;
}

bool comp(muchie a, muchie b)
{
	return a.cost < b.cost;
}

int root(subm id[], int u)
{
	if (id[u].parinte != u)
		return root(id, id[u].parinte );
	return u;
}

int uniune(subm id[], int u, int v)
{

	int x = root(id, u);
	int y = root(id, v);

	if (x == y)
		return -1;


	if (id[x].h < id[y].h)
	{
		id[x].parinte = y;

	}
	else if (id[x].h > id[y].h)
	{
		id[y].parinte = x;
	}
	else 
	{
		id[y].parinte = x; 
		id[x].h ++; 
	}
	return 1;
}


subm *id = new subm[200005];
vector<muchie> muchii;

int main()
{

	int n, m,  i;

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

	f >> n >> m ;

	int x, y, c;

	muchie crt;
	crt.ama = false;

	for (i = 0; i < m; i++)
	{
		f >> x >> y >> c;

		/*citim fiecare muchie*/
		crt.u = x;
		crt.v = y;
		crt.cost = c;

		muchii.push_back(crt);
	}

	/*sortam crescator dupa cost*/
	std::sort(muchii.begin(), muchii.end(), comp);

	/*configuram vecotrul de submultimi
	Initial, fiecare nod va fi intr-o submultime proprie*/
	for ( i = 1; i <= n ; i++)
		id[i].parinte =  i;

	long long ctot = 0; 
	int totama = 0; 

	for (i = 0; i < m ; i++)
	{
		crt = muchii[i];

		int rez = uniune(id, crt.u, crt.v);

		if (rez == 1)
		{
			totama ++ ;
			ctot = ctot + crt.cost;

			muchii[i].ama = true;
		}
	}
	g << ctot << "\n";
	g << totama << "\n";
	for (i = 0; i < m; i++)
		if (muchii[i].ama)
			g << muchii[i].u <<" "<< muchii[i].v << "\n";

}