#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int n,m;
struct muchie{
	int x;
	int y;
	int pond;
};
vector<muchie>muchii;
void scrie(vector<muchie> muchii)
{
	int m = muchii.size();
	for (int i = 0; i < m; i++)
		cout << muchii[i].x << " " << muchii[i].y << " " << muchii[i].pond << "\n";
	cout << "\n";
}
void sort(vector<muchie> &muchii)
{
	int m = muchii.size();
	for (int i = 0; i < m - 1; i++)
		for (int j = i+1; j < m; j++)
		{
			if (muchii[i].pond>muchii[j].pond)
			{
				muchie aux = muchii[i];
				muchii[i] = muchii[j];
				muchii[j] = aux;
				//scrie(muchii);
			}
		}
}
int main()
{
	ifstream f("apm.in");
	f >> n>> m;
	int x, y,p;
	for (int i = 0; i < m; i++)
	{
		f >> x >> y >> p;
		muchie m;
		m.x = x;
		m.y = y;
		m.pond = p;
		muchii.push_back(m);
	}
	sort(muchii);
	//for (int i = 0; i < m; i++)
	//	cout << muchii[i].x<<" "<< muchii[i].y <<" "<< muchii[i].pond<<"\n";

	vector<muchie> apm_muchii;
	int *fathers = new int[n];
	for (int i = 1; i <= n; i++)
		fathers[i] = i;
	int cost = 0;
	for (int i = 0; i < m; i++)
	{
		muchie mu = muchii[i];
		if (fathers[mu.x] != fathers[mu.y])
		{
			apm_muchii.push_back(mu);
			cost += mu.pond;
			for (int j = 1; j <= n; j++)
				if (fathers[j] == fathers[mu.x])
					fathers[j] = fathers[mu.y];
			if (apm_muchii.size() == n - 1)
				break;
		}
	}
	//cout << "\n";
	//cout <<"Cost:"<< cost << "\n";
	//scrie(apm_muchii);
	ofstream g("apm.out");
	g << cost;
	g << apm_muchii.size();
	for (int i = 0; i < apm_muchii.size(); i++)
		g << apm_muchii[i].x << " " << apm_muchii[i].y << "\n";
	f.close();
	g.close();
	return 0;
}