#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
using namespace std;

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

int disjoint[200010];

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

		return disjoint[x];
	}
}

bool same_set(int x, int y)
{
	return getRoot(x) == getRoot(y);
}

void join(int x, int y)
{
	int r1 = getRoot(x);
	int r2 = getRoot(y);

	if (!same_set(r1,r2))
		disjoint[r1] = r2;

}

struct Edge
{
	int x, y, w;

	Edge(int x, int y, int w)
	{
		this->x = x;
		this->y = y;
		this->w = w;
	}

};

vector<Edge> vec, res;
int main()
{


	int N, M;

	in >> N >> M;

	for (int i = 1; i <= M; ++i)
	{
		int x, y, w;
		
		in >> x >> y >> w;

		vec.push_back(Edge(x, y, w));

	}

	sort(vec.begin(), vec.end(), [&](const Edge &e1, const Edge &e2)
	{
		return e1.w < e2.w;
	});

	int c = 0;

	for (int i = 0; i < vec.size(); ++i)
	{
		if (!same_set(vec[i].x,vec[i].y))
		{
			c += vec[i].w, res.push_back(vec[i]);

			join(vec[i].x, vec[i].y);

		}
	}

	out << c << "\n";

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

	for (int i = 0; i < res.size(); ++i)
	{
		out << res[i].x << " " << res[i].y << "\n";
	}
	

	return 0;
}