#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream In("apm.in");
ofstream Out("apm.out");
vector<int> SolutionPos;
int* LeftEdges;
int* RightEdges;
int* Costs;
int* Groups;
int* Set;
int NodesNo;
int EdgesNo;
int SolutionNo;

void alloc()
{
	LeftEdges = new int[EdgesNo];
	RightEdges = new int[EdgesNo];
	Costs = new int[EdgesNo];
	Groups = new int[NodesNo];
	Set = new int[EdgesNo];
}

void dealloc()
{
	delete[] LeftEdges;
	delete[] RightEdges;
	delete[] Costs;
	delete[] Groups;
}

void init()
{
	for (int i = 0; i != NodesNo; ++i)
		Groups[i] = i;
}

void readData()
{
	In >> NodesNo >> EdgesNo;
	alloc();
	init();

	for (int i = 0, x, y, c; i != EdgesNo; ++i)
	{
		In >> x >> y >> c;

		LeftEdges[i] = x - 1;
		RightEdges[i] = y - 1;
		Costs[i] = c;
		Set[i] = i;
	}

	In.close();
}

void printData()
{
	Out << SolutionNo << "\n" << NodesNo - 1 << "\n";
	
	for (int i = 0; i != NodesNo - 1; ++i)
		Out << LeftEdges[SolutionPos[i]] + 1 << " " << RightEdges[SolutionPos[i]] + 1 << "\n";

	Out.close();
}

int getGroup(const int& pos)
{
	if (Groups[pos] == pos)
		return pos;

	return Groups[pos] = getGroup(Groups[pos]);
}

void uniteByEdges(const int& pos)
{
	Groups[getGroup(LeftEdges[pos])] = getGroup(RightEdges[pos]);
}

bool compareEdgesByCost(const int& e1, const int& e2)
{
	return Costs[e1] < Costs[e2];
}

bool sameGroupByEdges(const int& pos)
{
	return getGroup(LeftEdges[pos]) == getGroup(RightEdges[pos]);
}

void solve()
{
	sort(Set, Set + EdgesNo, compareEdgesByCost);

	for (int i = 0; i != EdgesNo; ++i)
		if (!sameGroupByEdges(Set[i]))
		{
			SolutionNo += Costs[Set[i]];
			uniteByEdges(Set[i]);
			SolutionPos.push_back(Set[i]);
		}
}

int main()
{
	readData();
	solve();
	printData();
	dealloc();

	//system("pause");
	return 0;
}