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

using namespace std;
typedef unsigned int uint;

ifstream fin("apm.in");
ofstream fout("apm.out");

class DisjointSet
{
	struct subset
	{
		uint root,rank;
	};
	vector<subset> DJ;
public:
	DisjointSet(const uint N);
	uint Find(uint x);
	void Union(uint x, uint y);
};

DisjointSet::DisjointSet(const uint N)
{
	for (uint i = 0; i <= N; ++i)
		DJ.push_back({i,1});
}

uint DisjointSet::Find(uint x)
{
	if (DJ[x].root != x)
		DJ[x].root = Find(DJ[x].root);
	return DJ[x].root;
}

void DisjointSet::Union(uint x, uint y)
{
	if (DJ[x].rank > DJ[y].rank)
	{
		DJ[x].rank = DJ[y].rank;
		DJ[y].root = x;
	}
	else
	{
		DJ[y].rank = DJ[x].rank;
		DJ[x].root = y;
	}
}

class Graph
{
	struct edge
	{
		uint src,dest;
		int cost;
	};
	uint V;
	vector<edge> Edges;
public:
	Graph(const uint V);
	void Add_edge(uint x, uint y, int c);
	void Kruskal();
};

Graph::Graph(const uint V)
{
	this->V = V;
}

void Graph::Add_edge(uint x, uint y, int c)
{
	Edges.push_back({x,y,c});
}

void Graph::Kruskal()
{
	auto cmp = [](edge a, edge b)
	{
		return a.cost < b.cost;
	};
	sort(Edges.begin(), Edges.end(), cmp);

    DisjointSet Set(V);

	struct MST
	{
		uint x,y;
	};
	vector<MST> sol;

	int sum = 0;

	for (uint i = 0, cnt = 1; cnt < V; ++i )
	{
	    int a = Set.Find(Edges[i].src), b = Set.Find(Edges[i].dest);
		if (a != b)
		{
			sum += Edges[i].cost;
			Set.Union(a, b);
			sol.push_back({Edges[i].src, Edges[i].dest});
			++cnt;
		}
	}

	fout << sum << '\n' << sol.size() << '\n';
	for (auto &i : sol)
		fout << i.x << ' ' << i.y << '\n';
}

int main()
{
	uint n,m;
	fin >> n >> m;

	Graph G(n);

	{
	    int c;
		for (uint x,y,i = 0; i < m; ++i)
		{
			fin >> x >> y >> c;
			G.Add_edge(x,y,c);
		}
	}

	G.Kruskal();
}