#include<fstream>
#include<vector>
#include<unordered_map>
#include<algorithm>
#include<string.h>
using namespace std;

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

int cost = 0;

struct Edge
{
	int x, y, v;

	Edge(int x, int y, int v) :x(x), y(y), v(v) {}

	Edge() {
		x = y = v = 0;
	}

};


Edge edges[400010];

int disjoint[200010];

vector<pair<int,int> > result;

bool comparator(const Edge &e1, const Edge &e2)
{
	return e1.v < e2.v;
}

int father(int x)
{
	if (!disjoint[x])
		return x;
	else
		disjoint[x] = father(disjoint[x]);
}

bool reunion(int x, int y)
{
	int f1 = father(x);
	int f2 = father(y);

	if (f1 != f2)
	{
		disjoint[f1] = f2;
		return true;
	}
	return false;
}

int main()
{

	int N, M;

	in >> N >> M;

	for (int i = 1; i <= M; ++i)
	{
		int x, y, v;

		in >> x >> y >> v;

		edges[i] = Edge(x, y, v);
		
	}

	sort(edges + 1, edges + M + 1, comparator);


	for (int i = 1; i <= M; ++i)
	{
		if (reunion(edges[i].x, edges[i].y))
			cost += edges[i].v, result.push_back(make_pair(edges[i].x,edges[i].y));
	}

	out << cost<<"\n";

	out << result.size() << "\n";

	for (int i = 0; i < result.size(); ++i)
		out << result[i].first << " " << result[i].second << "\n";

	return 0;
}