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

#define NMAX 200200
#define MMAX 400400


using namespace std;

struct muchie{ int cost, x, y; };

muchie A[MMAX];

int N, M, PMD[NMAX], costMinim;
vector<int> Solutie;

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

int Multime(int i)
{
	if (PMD[i] == 0) return i;
	else 
	{
		PMD[i] = Multime(PMD[i]);
		return PMD[i];
	}
}

void Reuneste(int i, int j)
{
	PMD[Multime(i)] = Multime(j);
}

void Citire(void)
{
	ifstream fin("apm.in");

	int i;
	
	fin >>N >>M;
	
	for (i = 1; i <= M; i++)
		fin >>A[i].x >>A[i].y >>A[i].cost;
	
	fin.close();
}

void Kruskal(void)
{
	sort(A+1, A+M+1, sortare);
	
	int i;
	
	for (i = 1; i <= M; i++)
	{
		if (Multime(A[i].x) != Multime(A[i].y))
		{
			costMinim += A[i].cost;
			Solutie.push_back(i);
			Reuneste(A[i].x, A[i].y);
		}
	}
}

void Afiseaza(void)
{
	ofstream fout("apm.out");
	
	int i;
	
	fout <<costMinim <<'\n' <<N-1 <<'\n';
	
	for (i = 0; i < Solutie.size(); i++)
		fout <<A[Solutie[i]].x <<' '<<A[Solutie[i]].y <<'\n';
	
	fout.close();
}

int main()
{
	Citire();
	
	Kruskal();
	
	Afiseaza();
	
	return 0;
}