#include <vector>
#include <algorithm>
#include <list>
#include <fstream>
#include <stack>
#include <iostream>
#include <utility>
#include <tuple>
#include <numeric>
using namespace std;

typedef pair<int,int> Pair;
vector<unsigned int> colors;
int grupa(int i)
{
	if (colors[i] == i) return i;
	colors[i] = grupa(colors[i]);
	return colors[i];
}
void reuniune(int i, int j)
{
	colors[grupa(i)] = grupa(j);
}

int main()
{
	//vector< vector <pair<int, int> > > adj(n,vector<Pair>());
	int n,m,i;
	ifstream fin("apm.in");
	fin >> n>>m;

	vector<tuple<int, int, int> > edges;
	edges.reserve(m);
	colors.resize(n+1);
	iota(colors.begin(), colors.begin()+n+1, 0);
	int a, b,w;
	for (int i = 0; i < m; i++)
	{
		fin >> a >> b >> w;
		edges.push_back(make_tuple(w, a, b));
	}
	sort(edges.begin(), edges.end());
	int chosen_color, replaced_color;
	int totalWeight = 0;
	vector<pair<int, int> > rasp;
	rasp.reserve(n - 1);
	for (i=0;i<m;i++)
	{
		w = get<0>(edges[i]);
		a = get<1>(edges[i]);
		b = get<2>(edges[i]);
		if (grupa(a) != grupa(b)) {
			chosen_color = min(a, b);
			replaced_color = max(a, b);
			totalWeight += w;

			reuniune(replaced_color,chosen_color);
			rasp.push_back(make_pair(replaced_color, chosen_color));
		}
	}
	ofstream fout("apm.out");
	fout << totalWeight<<endl;
	for (i = 0; i < n - 1; i++)
		fout << rasp[i].first << " " << rasp[i].second << endl;
}